NOIp模拟赛18/7/20 ksum 题解【前缀和】【堆】

作者: wjyyy 分类: ,解题报告,贪心 发布时间: 2018-07-20 19:45

点击量:30

 

   思维量比较大的一个题。

 

题目背景

\(\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解释:

测试点编号
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\)的数据来说,$latex \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;
}

说点什么

avatar
  Subscribe  
提醒
/* */