16.10.7 A:4815. 【NOIP2016提高A组五校联考4】ksum

这道题目仔细想想就可以发现是一个堆，我们先做1~n的前缀和，然后我们把（1，n）放入堆，[a+1,b]和[a,b-1]才有可能成为下次取出的对
象，那么我就将[a+1,b]和[a,b-1]加进堆，这样重复 k 次即可,另外，如果每次都[a+1,b]和[a,b-1]加入堆，会得到重复的答案，那么，我们可以固定左端点。

反正c++优先队列爱怎么浪怎么堆怎么浪，就酱紫。

#include<cstdio>
#include<queue>
#define F(i,x,y) for(ll i=x;i<=y;i++)
#define d(i,x,y) for(ll i=x;i>=y;i--)
using namespace std;
typedef long long ll;
const ll maxn = 100000 + 200;
ll a[maxn];
ll sum[maxn];
ll n,k;
struct node
{
    ll l,r;
    friend bool operator<(node x,node y)
    {
      return (sum[x.r] - sum[x.l-1]) < (sum[y.r] - sum[y.l-1]);
    }
}x;
priority_queue<node> q;
inline ll read()
{
    char ch = getchar();
    ll data = 0;

    while(ch<'0' || ch>'9')
     ch = getchar();

    while(ch>='0' && ch<='9')
    {
        data = data * 10 + ch - '0';
        ch = getchar();
    }

    return data;
} 
int main()
{
    freopen("ksum.in","r",stdin);
    //freopen("ksum.out","w",stdout);

    n = read(),k = read();

    x.l = 1;
    x.r = n;

    sum[0] = 0;
    F(i,1,n)
     a[i] = read(),sum[i] = sum[i-1] + a[i];

    q.push(x);

    d(i,k,1)
    {
        x = q.top();
        q.pop();

        printf("%lld ",sum[x.r] - sum[x.l-1]);

        if(x.r==n)
        {
            x.l++;
            q.push(x);
            x.l--;
        }
        x.r--;
        q.push(x);
    }
    printf("\n");
    return 0;
}