10.27T1 堆贪心

#3859 数组

描述

Peter喜欢玩数组。NOIP这天，他从Jason手里得到了大小为n的一个正整数数组。

Peter求出了这个数组的所有子段和，并将这n(n+1)/2个数降序排序，他想知道前k个数是什么。

输入

输入数据的第一行包含两个整数 n 和 k。

接下来一行包含 n 个正整数，代表数组。

输出

输出 k个数，代表降序之后的前k个数，用空格隔开。

样例输入[复制]

3 4
1 3 4

样例输出[复制]

8 7 4 4

提示

【输入输出样例2】

ksum.in

3 3

10 2 7
ksum.out

19 12 10

考虑求前缀和

实际上就是求前缀和相减的前k大

所以我考虑维护两个数组，一个数组是sum，另一个是相反数从大到小排序

这样就变成了序列合并求前k大的问题了

因为对于序列第一个数字肯定是要加进去的，所以我们就在堆里面先放入A1+B1~n这么多的数字，每次取出来一个Ai+Bj我们就可以把A(i+1)+Bj放进去维护

然后从堆顶取k次就可以了

官方解法差不多：

我们可以发现，如果当前最大的是[l,r]字段，那么易得[l,r+1]子段和[l-1,r]子段一定之前就已经取出。

而且最大的子段一定是[1,n],我们把子段加进一个堆，假设当前堆顶是[a,b],这次之后，[a+1,b]和[a,b-1]才有可能成为下次取出的对象，那么我就将[a+1,b]和[a,b-1]加进堆，这样重复 k 次即可。

代码我分了段所以可以只看后面部分

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<queue>
 5 using namespace std;
 6 long long b[1000006],sum[100005],a[1000005],fsum[1000005];
 7 long long n,k;
 8 struct node{
 9     long long x,y;
10     bool operator<(const node&t)const{
11         return sum[x]+fsum[y]<sum[t.x]+fsum[t.y];
12     }
13 };
14 priority_queue<node>q;
15 long long read(){
16     long long x=0,f=1;
17     char c=getchar();
18     while(!isdigit(c)){
19         if(c=='-')f=-1;
20         c=getchar();
21     }
22     while(isdigit(c)){
23         x=(x<<3)+(x<<1)+c-'0';
24         c=getchar();
25     }
26     return x*f;
27 }
28 int main() {
29     freopen("ksum.in","r",stdin);
30     freopen("ksum.out","w",stdout);
31     n=read(),k=read();
32     if(n<=1000) {
33         for(long long i=1; i<=n; i++) {
34             a[i]=read();
35             sum[i]=sum[i-1]+a[i];
36         }
37         long long tot=0;
38         for(long long i=0; i<=n; i++) {
39             for(long long j=i+1; j<=n; j++) {
40                 b[++tot]=sum[j]-sum[i];
41             }
42         }
43         sort(b+1,b+tot+1);
44         for(long long i=1; i<=k; i++) {
45             cout<<b[tot-i+1]<<" ";
46         }
47         return 0;
48     } else {
49         for(long long i=1; i<=n; i++) {
50             cin>>a[i];
51             sum[i+1]=sum[i]+a[i];
52         }
53         for(long long i=1;i<=n+1;i++)fsum[i]=-sum[i];
54         reverse(sum+1,sum+n+2);
55         for(long long i=1;i<=n;i++){
56             node temp;
57             temp.x=1;
58             temp.y=i;
59             q.push(temp);
60         }
61         while(k){
62             node u=q.top();
63             q.pop();
64             if(sum[u.x]+fsum[u.y]){
65                 k--;
66                 cout<<sum[u.x]+fsum[u.y]<<" ";
67             }
68             u.x++;
69             q.push(u);
70         }
71         return 0;
72     }
73 }

over