点击量：197

   思维量比较大的一个题。

目录

题目背景

$ \mathrm{Peter}$喜欢玩数组。$ \mathrm{NOIP}$这天， 他从$ \mathrm{Jason}$手里得到了大小为$ n$的一个数组。

 

题目描述

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

 

输入输出格式

输入格式：

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

 

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

输出格式：

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

 

输入输出样例

输入样例#1：

3 4

1 3 4

输出样例#1：

8 7 4 4

输入样例#2：

3 3

10 2 7

输出样例#2：

19 12 10

说明

输入输出样例1解释：

测试点编号	$n\le$	$k\le$
1	100	500
2	500	100000
3	1000	80000
4	1000	100000
5	10000	50000
6	20000	80000
7	50000	80000
8	100000	80000
9	100000	100000
10	100000	100000

对于所有数据， 满足$ 0<a_i\le 10^9,k\le \frac{n(n+1)}2,n\le 100000,k\le 100000$。

命题人:$ \mathrm{Jasonvictoryan}$

题解：

   对于$ n=100,000$的数据来说，$ \frac{n(n+1)}2 \approx 5,000,000,000$，无论如何都是不能枚举完的。因此我们要根据贪心，每次选最大的。

   我们根据$ a_i>0$，用a[u][v],u≤v来表示u到v区间和，那么a[i][j]一定严格大于a[i][j-1]和a[i+1][j]。因此我们选了a[i][j]，剩下两个才可用。而我们为了方便统一，当a[i][j]被选后，启用a[i+1][j]。

   那上面的过程怎么维护呢？我们因为每次要选最大的，所以用一个大根堆来维护。一开始把a[1][1],a[1][2],…,a[1][n]放入堆中，每次取最大值，最大值取出后将区间从左侧向右缩小，这样每次取出了最优情况，而把堆中元素控制在1e5以内。因为我们在选的过程中，只关注最大的是多少，而最大的被选后，它所遮盖的，也就是a[u+1…v][v]这些本比它小的元素，有可能变为最大。而且因为从u+1到v它们严格单调增，每次可用的都是最合法的。

   根据这样做下去，每次最优解就一定出现在可取线上了，而堆中维护的就是可取线上的元素。

   提交地址:https://www.luogu.org/problemnew/show/U31965

Code：

#include<cstdio>
#include<cstring>
#include<queue>
using std::priority_queue;
struct statu
{
    int l,r;
    long long sum;
    friend bool operator <(statu a,statu b)
    {
        return a.sum<b.sum;
    }
    statu(int l,int r,long long sum)
    {
        this->l=l;
        this->r=r;
        this->sum=sum;
    }
    statu(){}
};
priority_queue<statu> q;
long long a[101000];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
    }
    for(int i=1;i<=n;i++)
        q.push(statu(1,i,a[i]));
    for(int i=1;i<=k;i++)
    {
        statu p=q.top();
        q.pop();
        printf("%lld ",p.sum);
        q.push(statu(p.l+1,p.r,a[p.r]-a[p.l]));
    }
    return 0;
}