首页 > 代码库 > Codeforces 433C #248_div1_A 中位数的应用

Codeforces 433C #248_div1_A 中位数的应用

2024-07-10 10:39:07   220人阅读

擦。。今天这套题好尼玛难啊，做了一个小时，连一题都没做出来，而且还没什么头绪

查了下出题人，师大附中的 14年毕业 13年拿到的国家集训队资格 保送清华

题意是 给一串序列，计算一个值，这个值是 相邻两数的距离（或者说差的绝对值）的总和，你可以改变任意一种数（即序列里所有该数字全部变成另一个数），但只能改一次，使得刚刚要求得那个值最小。

要是只改一个数，那就很简单了，但是这个题是要改一种数，序列式乱序的，所求值跟相邻数有关，所以又不能随便打乱顺序。

然后就疯狂抓头。。

后来还是看的题解

其实题目里面改变一种数其实也很好处理，把该种数的相邻的数字都给存起来，然后就是看该数字跟这些m个数（假设为m个）的距离的最小了。根据以前数轴的思想，不难得出，只要把当前该x值，变成排序过后的m个数列中的中位数即可。因为中位数的性质就是跟所有序列数的距离和最小，这个用数轴思想很容易证明。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define LL __int64using namespace std;const int N = 100000+10;int A[N];int n,m;int vis[N];vector<int> v[N];int abs(int x){    if (x<0) return -x;    else return x;}int main(){    while (scanf("%d%d",&n,&m)!=EOF)    {        LL ans=0;        memset(vis,0,sizeof vis);        for (int i=1;i<=m;i++){          scanf("%d",&A[i]);          if (i>1){            if (A[i]!=A[i-1]){                v[A[i]].push_back(A[i-1]);                v[A[i-1]].push_back(A[i]);            }            ans+=(LL)abs(A[i]-A[i-1]);          }        }        LL maxn=0;        if (m>1)        for (int i=1;i<=m;i++){            if (vis[A[i]]) continue;            vis[A[i]]=1;            sort(v[A[i]].begin(),v[A[i]].end());            int r=v[A[i]].size();            if (r==0) continue;            r/=2;            int mid=v[A[i]][r];            LL t1=0;            LL t2=0;            for (int j=0;j<v[A[i]].size();j++){                t1+=(LL)abs(mid-v[A[i]][j]);            }            for (int j=0;j<v[A[i]].size();j++){                t2+=(LL)abs(A[i]-v[A[i]][j]);            }            maxn=max(maxn,t2-t1);        }        ans-=maxn;        printf("%I64d\n",ans);    }    return 0;}

 


联系
我们