士兵队列问题.cpp

王晓东算法设计与分析源码。vc下编译通过能够运行。且运行效率较高

#include<iostream>
#include<algorithm>
using namespace std;
int x[10000];
int y[10000];

int main()
{
 		int n;
 		cin >> n;
 		for(int i=0;i<n;i++)
 		cin >> x[i] >> y[i];
 		int tempx;
 		int tempy;
 		nth_element(y,y+n/2,y+n);
 		tempy = y[n/2];
 		sort(x,x+n);
 		for(int i=0;i<n;i++)
 		x[i]-=i;
 		nth_element(x,x+n/2,x+n);
 		tempx = x[n/2];
 		int total = 0;
 		for(int i=0;i<n;i++)
 		{
         total +=abs(y[i]-tempy);
         total +=abs(x[i]-tempx);
		 }
		 cout << total << endl;
		 system("pause");
}