题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1112
2019-3-2回来更新
发现我当时这个思想就是对顶堆，我还一直以为对顶堆多神奇…
STL大法好！！
最开始查了查题解，觉得好麻烦啊不想照着写…所以就自己搞了搞
550人AC 排在rank35 还算不错…
题意：把连续k个数每次+1或-1，用最少的操作次数变为同一个数
有一个显而易见结论：一定把这连续k个都变为这k个数的中位数是最优的
所以我们要实现的是：快速找到[中位数]，求出所有大于/小于[中位数]的数的和，并支持删除/插入一个数
看起来就像平衡树
但是不想打怎么办？ 用set！
set里的元素不可重，所以我们用pair，first存值，second存下标
我们用两个set来分别维护连续k个数的前一半和后一半(1 ~ k/2) (k/2+1 ~ k)
选中的连续k个数不断往后移，从1 ~ k到n-k+1 ~ n
因为set是有序的，所以第二个set的第一个数(也就是begin)就是我们要的中位数
中位数知道了，[和]我们可以insert的时候一边算出来，那么对于目前的序列的答案就知道了
插入/删除操作就直接通过set非常妙妙的erase就可以了，可以直接erase一个值/迭代器
所以插入/删除非常简单的就可以实现了
为了保证第一个set的元素全都小于等于第二个set里的，每次区间往后移了之后比较下s1.end()和s2.begin()，如果第一个大于第二个，我们就需要交换这两个元素
交换的过程和插入/删除非常的相似
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<bits/stdc++.h> #define MAXN 100010 #define pr pair<int,int> typedef long long ll; using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m,a[MAXN]; set<pr>s1,s2; set<pr>::iterator r1,r2; ll sum1,sum2,ans; pr tmp; int main(){ n=rd(),m=rd(); if(m==1){ puts("0"); return 0; } ans=LONG_LONG_MAX; for(int i=1; i<=n; i++)a[i]=rd(); for(int i=1; i<=m/2; i++)s1.insert(pr(a[i],i)),sum1+=a[i]; for(int i=m/2+1; i<=m; i++)s2.insert(pr(a[i],i)),sum2+=a[i]; for(int i=1; i+m-1<=n; i++){ r1=s1.end();r2=s2.begin();r1--; while((*r1).first>(*r2).first){ tmp=*r1;s1.erase(r1);s2.insert(tmp);sum1-=tmp.first;sum2+=tmp.first; tmp=*r2;s2.erase(r2);s1.insert(tmp);sum2-=tmp.first;sum1+=tmp.first; r1=s1.end();r2=s2.begin();r1--; } ll num=(*r2).first; ans=min(ans,num*(m/2)-sum1+sum2-num-num*(m-m/2-1)); tmp=pr(a[i],i); if(s1.find(tmp)!=s1.end())s1.erase(tmp),s1.insert(pr(a[i+m],i+m)),sum1=sum1-tmp.first+a[i+m]; else s2.erase(tmp),s2.insert(pr(a[i+m],i+m)),sum2=sum2-tmp.first+a[i+m]; } printf("%lld\n",ans); return 0; } |
数据生成器：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<bits/stdc++.h> #define MAXN 100010 #define pr pair<int,int> typedef long long ll; using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } inline void Srand(){ freopen("seed.txt","r",stdin); int seed; cin>>seed; fclose(stdin); srand(seed); seed=rand(); freopen("seed.txt","w",stdout); cout<<seed<<endl; fclose(stdout); freopen("in.txt","w",stdout); } ll Rand(){ ll num=rand()*10000+rand(); return (num+1000000)%1000000+1; } int n,m; int main(){ Srand(); int n=100000,m=rand()%n+1; cout<<n<<' '<<m<<endl; while(n--){ printf("%lld\n",Rand()); } return 0; } |
