1 条题解

  • 0
    @ 2025-10-8 16:55:52
    #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

    *【中位数】[CEOI 1998] 士兵站队

    信息

    ID
    1257
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    136
    已通过
    44
    上传者