【NOIP2016提高A组五校联考4】ksum

Description

给定一个长度为N的数组，求出前K大字段和
详见样例解释

Input

第一行两个数N和K，表示数组长度为N，求前K大的字段和

Output

k个数，前K大的字段和

Sample Input

样例输入1：
3 4
1 3 4
样例输入2：
3 3
10 2 7

Sample Output

样例输出1：
8 7 4 4
样例输出2：
19 12 10
【NOIP2016提高A组五校联考4】ksum

Solution

这是一道水题！然而我做了三个小时！！
由于a[i]>0，所以越长的字段和越大。
那么用堆维护，一开始只把1~n加入，之后每次弹出堆顶的元素后，把它代表的区间去掉最后一个变成小区间，重新加入堆，就行了。对于每种大小的最后一个区间，不仅要去最后一个，也要将去掉第一个的区间加入

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
using namespace std;
int n,m,k;
ll a[N],s[N],tot=0;
struct node{
int x,y;
    ll d;
};
node h[N*10];
void down(int x)
{
int y=x*2;if(y<tot&&h[y+1].d>h[y].d) y++;
if(y>tot) return;
if(h[y].d>h[x].d) swap(h[x],h[y]),down(y);
}
void up(int x)
{
if(x==1) return;
if(h[x].d>h[x/2].d) swap(h[x],h[x/2]),up(x/2);
}
void insert(int x,int y,ll z)
{
    h[++tot].x=x;h[tot].y=y;h[tot].d=z;up(tot);
}
int main()
{
    freopen("ksum.in","r",stdin);freopen("ksum.out","w",stdout);
scanf("%d%d",&n,&k);
    fo(i,1,n) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    h[++tot].d=s[n];h[tot].x=1;h[tot].y=n;
    fo(i,1,k)
    {
int x=h[1].x,y=h[1].y;
printf("%lld ",h[1].d);
        swap(h[1],h[tot]);tot--;down(1);
if(y-x>0)
        {
            insert(x,y-1,s[y-1]-s[x-1]);
if(y==n) insert(x+1,y,s[y]-s[x]);
        }
    }
    fclose(stdin);fclose(stdout);
}

秒客网