Time Limit: 10 second
Memory Limit: 2 MB
问题描述
在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。 士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。 按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。 如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。
编程任务：
计算使所有士兵排成一行需要的最少移动步数。
Input
由文件 input.txt 提供输入数据。文件的第1行是士兵数n，1≤n≤10000。 接下来n行是士兵的初始位置，每行2个整数x和y，-10000≤x，y≤10000。
Output
将计算结构输出到文件output.txt.文件的第一行中的数是士兵排成一行需要的最 少步数。
Sample Input
3 -4 -3 -4 5 5 2
Sample Output
16
【题解】
首先。要让这些士兵都站到同一行。
先对y坐标进行排序。
然后对于它们最后要站的行号k;
S=|a[1].y-k|+|a[2].y-k|+...+|a[n].y-k|;
要让S最小。
想想都能知道k是a[1..n].y的中位数。
答案累加上|a[i]-k|;
这样这些士兵就全都在一行上了。这个问题被转化为一个一维的问题了
然后是在列上的位置。
我们同样对a[i].x进行升序排序。
然后我们可以确定a[1].x,a[2].x,a[3].x。。。。a[n].x
这些位置上的士兵对应最后答案的k,k+1,k+2...k+n-1这些位置。
因为凭感觉就能知道这样比较优。(难道a[n].x还要对应k吗？？)；
然后S=|a[1].x-k|+|a[2].x-(k+1)|+|a[3].x-(k+2)|...+|a[n].x-(k+n-1)|;
同样要让S最小。
我们把S的表达式做一些改变。
S=|a[1].x-k|+|(a[2].x-1)-k|+|(a[3].x-2)-k|+...+|(a[n].x-(n-1))-k|
然后我们令b[i] = a[i].x-i+1;
S=|b[1]-k|+|b[2]-k|+...+|b[n]-k|;
没错。这又变成求y轴的方法了。
获得b数组之后再对b数组进行一次升序的排序。
然后获得中位数k,再累加|b[i]-k|即可。
这里可以不用再定义一个b数组，直接在a数组的基础上处理一下就好即-i+1;
只有一维的x坐标的情况。你可以理解为。就是把k+1,k+2..k+n-1这些位置全部都移到
了k这个位置。然后本来要在k+1的人，先减去1然后再移到k时就相当于移到k+1了。
本来要在k+2的人同理。
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
struct point //用于储存输入的点
{
int x, y;
};
int n, ans = 0;
point a[10001 + 100]; //开大点没关系的。
void input_data()
{
scanf("%d", &n); //输入n个士兵的位置。
for (int i = 1; i <= n; i++)
scanf("%d%d", &a[i].x, &a[i].y);
}
int cmp1(const point &a, const point &b) //比较函数1，这是y轴的
{
if (a.y < b.y)
return 1;
return 0;
}
int cmp2(const point &a, const point &b) //这是x轴上的。
{
if (a.x < b.x)
return 1;
return 0;
}
int abs(int x) //获取一个数的绝对值。
{
return x < 0 ? -x : x;
}
void get_ans1()
{
int mid = a[(n + 1) / 2].y; //这是竖直方向上的k值。
for (int i = 1; i <= n; i++) //累加即可得到S；
{
ans += abs(a[i].y - mid);
a[i].y = mid; //这一步没有意义，但是能让思路更清晰。表示全都在一行上面了。
}
}
void get_ans2() //这是x轴上的一维情况
{
for (int i = 1; i <= n; i++) //先减去i再加上1.
a[i].x = a[i].x - i + 1;
sort(a + 1, a + 1 + n, cmp2); //相当于给b数组排序。
int mid = a[(n + 1) / 2].x; //同样获取k。
for (int i = 1; i <= n; i++)//累加a[i].x-k的绝对值即可。
ans += abs(a[i].x - mid);
}
void output_ans()
{
printf("%d
", ans); //最后输出答案。
}
int main()
{
input_data();
sort(a + 1, a + 1 + n, cmp1);//对y坐标进行排序
get_ans1();
sort(a + 1, a + 1 + n, cmp2);//对x坐标进行升序排
get_ans2();
output_ans();
return 0;
}