先從一到簡單的題看起：

士兵站隊問題

在一個劃分成網格的操場上，n個士兵散亂地站在網格點上。網格點由整數坐標(x,y)表示。士兵們可以沿網格邊上、下、左、右移動一步，但在同一時刻任一網格點上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個水平隊列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何選擇x和y的值才能使士兵們以最少的總移動步數排成一列。

分析:這個問題我們可以把X，Y分開看，兩者互不影響。其實就是求所以橫坐標的中點，也就是中位數，那么為什么呢？

我們可以把所選定的位置左右的兩個點看成一對，只要所選位置在兩者之間，那么長度恒等于兩點的線性距離和，所以我們可以根據每一對不斷縮小我們所選位置的范圍，最后如果有奇數個點，那么就會在中間的那個點上，如果是偶數那么在中間兩個數和他們所構成的區間，這樣想就容易發現中位數這一規律了。

?

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int x[10010],y[10010]; int main() {freopen("sol.in","r",stdin);freopen("sol.out","w",stdout);int n,i,sum=0,s;cin>>n;for (i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);sort(x+1,x+n+1);sort(y+1,y+n+1);s=y[(1+n)/2];for (i=1;i<=n;i++)sum+=abs(y[i]-s);for (i=1;i<=n;i++)x[i]-=i;sort(x+1,x+n+1);s=x[(1+n)/2];for (i=1;i<=n;i++)sum+=abs(x[i]-s);cout<<sum<<endl;fclose(stdin);fclose(stdout);return 0; }

再看看中位數與動歸結合的應用：

[問題描述]

一些村莊被建在一條筆直的高速公路邊上。我們用一條坐標軸來描述這條高速公路，每一個村莊的坐標都是整數。沒有兩個村莊坐標相同。兩個村莊間的距離，定義為它們坐標值差的絕對值。

人們需要在一些村莊建立郵局——當然，并不是每一個村莊都必須建立郵局。郵局必須被建在村莊里，因此它的坐標和它所在的村莊坐標相同。每個村莊使用離它最近的那個郵局，建立這些郵局的原則是：所有村莊到各自所使用的郵局的距離總和最小。

你的任務是編寫一個程序，在給定了每個村莊的坐標和將要建立的郵局數之后，按照上述原則，合理地選擇這些郵局的位置。

輸入文件的文件名是post.in

文件的第輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

一行是包含兩個整數：第一個整數是村莊的數目V，1〈=V〈=300，第二個整數是將建立的郵局數P，1〈=P〈=30且P〈=V。

文件的第二行按照遞增順序列出了V個整數。這V個整數分別表示了各村莊的位置坐標。對于每一個位置坐標X，1〈=X〈=10000。

輸出文件名是post.out

文件的第一行是一個整數S，表示你所求出的所有村莊到離它最近郵局的距離的總和。

相應地，文件的第二行按照遞增順序列出了P個整數，分別表示你所求出每個郵局的建立位置。雖然對于同一個S，可能會有多種郵局建立的方案，但只需輸出郵局位置盡量靠前的一組。

Example

Post.in

10???5

1 2 36 7 9 11 22 44 50

Post.out

9

2 7 2244 50?

這一道題是很經典的區間動態規劃題，在預處理中就用到了上述思想。

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,m,len[320][320],f[320][320],a[320],s[320][320],m1[320][320]; void print(int x,int y) {if (x==0)return;print(x-1,s[x][y]);printf("%d ",a[m1[s[x][y]+1][y]]); } int main() {freopen("post.in","r",stdin);freopen("post.out","w",stdout);int i,j,k;scanf("%d%d",&n,&m);for (i=1;i<=n;i++)scanf("%d",&a[i]);for (i=1;i<=n;i++)for (j=i;j<=n;j++){m1[i][j]=(i+j)/2;int temp1=0;for (k=i;k<=j;k++){len[i][j]+=abs(a[k]-a[m1[i][j]]);}}memset(f,127,sizeof(f));for (i=1;i<=n;i++){f[1][i]=len[1][i];s[1][i]=0;}for (i=2;i<=m;i++)for (j=i;j<=n;j++)for (k=i-1;k<=j-1;k++)if (f[i][j]>f[i-1][k]+len[k+1][j]){f[i][j]=min(f[i][j],f[i-1][k]+len[k+1][j]);s[i][j]=k;}cout<<f[m][n]<<endl;print(m,n);return 0; }

中位數解決了，那么就來看一下帶權中位數問題，這個問題如果不知道，一定會覺得某些題十分的高大上，無從下手。例如

典型的帶權中位數問題，把平面轉成線性即可。為何帶權中位數問題就是就權值的中位數呢，我們可以這么想，不帶權的相當于權為1，每個點只有一個人，那么帶權就相當每個點有該點權值個人，這樣理解就與上面的思路神合了
ps:證明過程
若最優點在T
則有:
∑{D*DIST(I，T)}(I<>T)<=∑{D*DIST(I,T+1)}(I<>T+1)
將此式化為:
∑{D[L]}*DIST(L,T)}+∑{D[R]*DIST(R,T)}+D[T+1]*DIST(T+1,T)
<=∑{D[L]}*DIST(L,T+1)}+∑{D[R]*DIST(R,T+1)}+D[T]*DIST(T,T+1) (L<T&R>T+1)
即:
∑{D[L]*DIST(L,T+1)}-∑{D[L]*DIST(L,T)}(L<T)+D[T]*(DIST(T,T+1))>=∑{D[R]*DIST(R,T)}-∑(D[R]*DIST(R,T+1))(R>T+1)+D[T+1]*(DIST(T,T+1))進一步化簡為:
∑{D[L]*(DIST(L,T)-DIST[L,T+1])}(L<=T)<=∑{D[R]*(DIST(R,T+1)-DIST(R,T))}(R>=T+1)∵DIST(L,T)-DIST(L,T+1)=DIST(T,T+1)
DIST(R,T+1)-DIST(R,T)=DIST(T+1,T)
OBVIOUSLY : DIST(T,T+1)=DIST(T+1,T)
因此:
∑D[L](L<=T)>=∑(D[R])(R>=T+1)
即:∑D[L](L<T)+D[T]>=∑(D[R])(R>T)
因此我們發現，若T是最優點，則必有其左邊的權值和加上D[T]后大于右邊的權值和
而類似的，我們可以證明其右邊的權值和加上D[T]后大于左邊的權值和
因此我們要找的點也就是滿足以上條件的點。注意到此時我們的選擇已經和具體的位置(坐標)沒有關系了，而成為主要考慮因素的僅僅是各點上的權值。
因為左邊的權值和數+D[T]>=右邊的權值和，那么:
LEFTSUM+D[T]>=RIGHTSUM=SUMALL-(LEFTSUM+D[T])
=>2*(LEFTSUM+D[T])>=SUMALL
=>2*RIGHTSUM<=SUMALL
同理可得:
RIGHTSUM+D[T]>=LEFTSUM=SUMALL-(RIGHTSUM+D[T])
=>2*(RIGHTSUM+D[T])>=SUMALL
=>2*LEFTSUM<=SUMALL
此時我們發現:
2*LEFTSUM<=SUMALL 而 2*(LEFTSUM+D[T])>=SUMALL
也即是說當前的位置T上的數包含了第[(SUMALL)/2]個數，由開篇的簡述可知，這第[(SUMALL)/2]個數，就是這個序列中的帶權中位數。所以這一類問題，實質上就是帶權中位數問題。
?

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; struct data {int x,y,w; };data num[50003]; int n,i,j,k; double sum,ans,xx,yy; int xl,yl; int cmp(data a,data b) {return a.x<b.x; } int cmp1(data a,data b) {return a.y<b.y; } int main() {freopen("ball.in","r",stdin);freopen("ball.out","w",stdout);scanf("%d",&n);sum=ans=xx=yy=0;for (i=1;i<=n;i++){scanf("%d",&num[i].w);sum+=num[i].w;}for (i=1;i<=n;i++)scanf("%d%d",&num[i].x,&num[i].y);sort(num+1,num+n+1,cmp);double mid=sum/2;for (i=1;i<=n;i++){xx+=num[i].w;if (xx>mid){xl=num[i].x;break;}}for (i=1;i<=n;i++)ans+=num[i].w*(abs(num[i].x-xl));sort(num+1,num+n+1,cmp1);for (i=1;i<=n;i++){yy+=num[i].w;if (yy>mid){yl=num[i].y;break;}}for (i=1;i<=n;i++)ans+=num[i].w*(abs(num[i].y-yl));printf("%0.2lf",ans); }

原博客鏈接：鏈接

總結

以上是生活随笔為你收集整理的中位数及带权中位数问题（转）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。