1 条题解
-
0
#include<bits/stdc++.h> using namespace std; struct node{int x,y;}a[11000]; bool cmp(node a,node b){return a.y<b.y;} bool cmp1(node a,node b){return a.x<b.x;} int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); int ans=0; sort(a+1,a+n+1,cmp); int mid=a[(n+1)>>1].y; for(int i=1;i<=n;i++) ans+=abs(mid-a[i].y); sort(a+1,a+n+1,cmp1); for(int i=1;i<=n;i++) a[i].x-=i; /* 这里的 x[ i ] - i并不是离散化.... 对x进行排序后,要求使得士兵全部相邻的最小移动次数.那么在移动前和移动后,士兵的相对位置是不变的. 举例来说,记add为移动后的最左端的士兵的前一位置 x[ 1 ] -> add + 1; x[ 2 ] -> add + 2; … x[ n ] -> add + n; 转换一下 x[ 1 ] - 1 -> add; x[ 2 ] - 2 -> add; … x[ n ] - n -> add; 这就转化为了跟y轴一样的问题了 */ sort(a+1,a+n+1,cmp1); mid=a[(n+1)>>1].x; for(int i=1;i<=n;i++) ans+=abs(mid-a[i].x); printf("%d\n",ans); return 0; }
- 1
信息
- ID
- 1257
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 136
- 已通过
- 44
- 上传者