$ POJ~1723~Soldiers $ (中位数)
$ solution: $
这道题说难也不算太难，但是当时自己想的很矛盾。所以还是列一篇题解。
这道题首先比较容易看出来的就是：行和列是两个分开的问题，而且行的移动就是一个仓库选址的板子，直接求中位数就好。
这题难就难在列，因为列要求相邻，如果某一个格子上有多个士兵，他们要分开站位。这个题看到正解后我真的很想敲自己一下，明明之前就很在意如何消除这种与坐标有关的后效性时可以用权值 $ -i $ 的方法，但是还是忘了。这道题我们考虑不看中点，它的后效性极大！我们看左端点。
假设左端点为 $ k $ ，那么我们将每个士兵按横坐标排序，显然最终状态时，起始越左边的士兵里这个左端点越近。于是我们列出答案方程： $ ans=\sum |a[i]-(k+i)| $ 嗯？这个式子怎么跟中位数（ $ ans=\sum |a[i]-k| $ ）的那么像？于是我们将每个士兵定义一个新权值 $ a[i]'=a[i]-i $ 然后再求中位数就好。这个就是上面博主说的用权值 $ -i $ 的方法消除与坐标有关的后效性。
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,ans;
int a[10005];
int b[10005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr();
for(rg i=1;i<=n;++i)
a[i]=qr(),b[i]=qr();
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(rg i=1;i<=n;++i)
a[i]-=i;
sort(a+1,a+n+1);
for(rg i=1;i<=n;++i){
ans+=abs(a[i]-a[n/2+1]);
ans+=abs(b[i]-b[n/2+1]);
}printf("%d\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/812-xiao-wen/p/11251672.html
相关资源：JAVA上百实例源码以及开源项目
