Description
Solution
这题不是明显的堆来模拟吗,然后在hash判个重就好了。
但是,这题要值得反思的是,我以前的人工堆有一个很致命的错误,就是堆顶退堆的时候,应该把堆底和堆顶交换,然后num–之后再down一下,这然才对,错误的就不说了。
还有一个问题就是:我不会用STL来实现多元的堆,这个还要学习一下。
Code
#include<iostream>
#include<cstdio>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const ll maxn=100007,mo=10000007;
ll i,j,k,t,n,m,ans,tot,shu;
ll a[maxn],l[maxn],r[maxn],sum[maxn];
ll h[mo];
bool hash(ll x,ll y){
ll o=(maxn*maxn%mo*x%mo+maxn*y%mo)%mo;
while(h[o]!=x&&h[o]!=0)o=(o+1)%mo;
if(!h[o]){h[o]=x;return 1;}
return 0;
}
void up(ll x){
while(x>1&&sum[x]>sum[x/2]){
swap(sum[x],sum[x/2]),swap(l[x],l[x/2]),swap(r[x],r[x/2]);
x/=2;
}
}
void down(ll x){
while(x*2<=tot&&sum[x*2]>sum[x]||x*2+1<=tot&&sum[x*2+1]>sum[x]){
ll y=x*2;
if(y+1<=tot&&sum[x*2+1]>sum[x*2])y++;
swap(sum[x],sum[y]),swap(l[x],l[y]),swap(r[x],r[y]);
x=y;
}
}
int main(){
freopen("ksum.in","r",stdin);
freopen("ksum.out","w",stdout);
scanf("%d%d",&n,&k);
fo(i,1,n)scanf("%d",&a[i]),t+=a[i];
sum[++tot]=t,l[tot]=1,r[tot]=n;
while(k--){
printf("%lld ",sum[1]);
if(l[1]==r[1]){
swap(sum[1],sum[tot]);swap(l[1],l[tot]);
swap(r[1],r[tot]);tot--;down(1);
continue;
}
if(hash(l[1]+1,r[1])){
sum[++tot]=sum[1]-a[l[1]];
l[tot]=l[1]+1,r[tot]=r[1];
up(tot);
}
if(hash(l[1],r[1]-1)){
sum[++tot]=sum[1]-a[r[1]];
l[tot]=l[1],r[tot]=r[1]-1;
up(tot);
}
swap(sum[1],sum[tot]);swap(l[1],l[tot]);
swap(r[1],r[tot]);tot--;down(1);
}
}