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

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

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

查了下出题人,师大附中的 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;}