POJ题目链接

N soldiers of the land Gridland are randomly scattered around the country.
A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).

最开始看这题想到的就是枚举队伍的起点、计算每个士兵移动到对应位置的最短路。题目中并没有确定士兵排队的顺序,那么如何确定士兵移动到的「对应位置」呢?显然,按照X坐标排序,第1个士兵移动到队伍的第1个,第2个士兵移动到第2个,……,第N个士兵移动到第N个位置。唯一有问题的是如果有多个士兵X坐标相同怎么办呢?容易证明,按照任意顺序这些士兵走的路加和相等。

然而枚举起点需要O((MaxX-MinX)²),计算士兵又需要O(N),时间复杂度接近10^12,肯定要超时。这时候我们会想到:能不能直接确定队伍的y坐标?如果我们不需要士兵移动到指定位置,只需要他们移动到队伍所在行(也就是在y轴方向移动),我们称此为「第一阶段」,怎样才能使士兵们「第一阶段」移动距离最小?假设队伍在第Y行,我们列出这样的式子:|Y1-Y|+|Y2-Y|+……+|Yn-Y|,这就是「第一阶段」需要移动距离总和。显然只要排序后Y取中位数就可以了。

但是这样的复杂度仍然是O(N²(MaxX-MinX)),最大达到210^8,还是要超时。这时候我们就会想到:能不能用类似的方法确定队伍起点的X坐标呢?仔细思考:如果队伍第一个横坐标为X,那么「第二阶段」需要移动距离总和就是:|X1-X|+|X2-(X+1)|+|X3-(X+2)|+……+|Xn-(X+n-1)|,变形得到:|X1-X|+|X2-1-X|+……+|Xn-n+1-X|,那么前面的Xi-i+1是可以构造的,排序取中位数又可以得到队伍第一个X坐标了!

还有一个问题是题目中规定:「Two or more soldiers must never occupy the same position at the same time. 」这个怎么解决?很简单,因为如果两个士兵X坐标不同,他们的路径一定不会相交;如果相同,有一个在前,更不会相交。

贴上代码:

#include
#include
#include
#include
using namespace std;
const int maxn=10005;
int n,midnum_x,midnum_y,tmp[maxn],ans=0;
struct WT{
    int x,y;
}a[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline bool cmp_by_y(WT aa,WT bb){
    return aa.y>1].y;
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++) tmp[i]=a[i].x-i+1;
    sort(tmp+1,tmp+1+n);
    midnum_x=tmp[(n+1)>>1];
    for (int i=1;i<=n;i++) ans+=getdst(a[i].x,a[i].y,midnum_x+i-1,midnum_y);
    printf("%d\n",ans);
    return 0;
}