AcWing 123. 士兵
原题链接
中等
作者:
cisdes
,
2022-04-02 10:07:47
,
所有人可见
,
阅读 171
//对于x应该构造新的绝对值式,设a为移动后x1到的位置则移动距离为|x1 - a| + |x2 - a + 1| + |x3 - a + 2| + |x4 - a + 3| +....
//需要注意的是每次都要进行排序
#include<iostream>
#include<algorithm>
using namespace std;
int x[100100];
int y[100100];
int len1,len2;
int ans1,ans2,res;
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i++)
{
cin>>x[i]>>y[i];
}
sort(x,x+n);
for(int i = 0;i < n;i++)
{
x[i] -= i;
}
sort(x,x+n);
sort(y,y+n);
int mid1 = x[n / 2];
int mid2 = y[n / 2];
for(int i = 0 ;i < n;i++) res += abs(mid1 - x[i]);
for(int i = 0 ;i < n;i++) res += abs(mid2 - y[i]);
cout<<res;
}