text1.cpp

计算机算法的士兵战队问题

#include <iostream.h> 
#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; 


//带权中位数的第一次用，因为y最后都是一样，所以向y移动的总步数要最少
//nth_element(y, y + n / 2, y + n); 
sort(y,y+n);
{for(i=0;i<n;i++)
cout<<y[i]<<"  ";}

tempy = y[n/2]; 

sort(x, x + n); 

 

//x最好是要不一样的，所以先假定他们排成0,1,2...
for( i = 0; i < n; i++) 
x[i] -= i; 

for(i=0;i<n;i++)
cout<<x[i]<<"  ";

//最后剩余的是offset，所以要选一个中位数（对上面的排列进行complete，使其成为最后真正的排列），使得各个offset到这个位置的总步数最少
//nth_element(x, x + n / 2, x + n); 
sort(x,x+n);
tempx= x[n/2]; 
cout<<tempx;

int total=0; 

for( i = 0; i < n; ++i) 
{ 
total += abs(y[i] - tempy); 
total += abs(x[i] - tempx); 
} 
cout<<total<<endl; 

}