首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。