2016 一中培训 day 5 ksum

2018-06-17 23:42:42来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

又是一天的爆零!!!!!

原本第一题 很容易做 竟然优化过度

丢了答案

1693: ksum

Time Limit
1000 ms
Memory Limit
524288 KBytes
Judge
Standard Judge
Solved
18
Submit
41
Submit Status

Description

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

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

Input Format

输入文件名为 ksum.in。

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

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

Output Format

输出文件名为 ksum.out。

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

Sample Input

input1
3 4
1 3 4

input2
3 3
10 2 7

Sample Output

output1
8 7 4 4

output2
19 12 10

Hint

测试点编号 n ≤ k ≤

1 100 5000

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

对于所有数据,满足 ai≤10 9 k≤n(n+1)/2,n≤100000,k≤100000

明显的堆维护 对于一段连续序列 它的一系列次小值 一定是这段序列的子集;

只要每次取出 堆顶 将堆顶序列分别由 (l+1,r)&&(l,r-1)的子序列塞入堆中

进行堆维护即可 注意过程可能出现重复顶点 用哈希表维护即可;

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#define maxn 100010
using namespace std;
struct st
{
    int l,r;
    long long sum;
}mu[2*maxn];
typedef pair<int,int> pa;
map <pa,bool>q1;
int n,m,k,l,n1,i;
int a[maxn];
void down(int x)
{
    int fa=x,son;
    while(fa*2<=n1)
    {
        son=fa*2;
        if(mu[son+1].sum>mu[son].sum&&son+1<=n1)son++;
        if(mu[fa].sum>mu[son].sum)break;
        swap(mu[fa],mu[son]);
        fa=son;
    }
}
void up(int x)
{
    int fa,son=x;
    while(son/2)
    {
        fa=son/2;
        if(mu[fa].sum>mu[son].sum)break;
        swap(mu[fa],mu[son]);
        son=fa;
    }
}
void push (st x)
{
    n1++; q1[pa(x.l,x.r)]=1;
    mu[n1]=x;
    up(n1);
}
int main()
{
//    freopen("ksum.in","r",stdin);
//    freopen("ksum.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        mu[1].sum+=a[i];
    }
    n1=1;mu[1].l=1;mu[1].r=n;q1[pa(mu[1].l,mu[1].r)]=1;
    for(i=1;i<=k;++i)
    {
        printf("%lld ",mu[1].sum);
        if(mu[1].l<mu[1].r)
        {
            st q;
            q=mu[1];
            q.sum-=a[q.l];
            q.l++;
            if(!q1[pa(q.l,q.r)])
            push(q);
            q=mu[1];
            q.sum-=a[q.r];
            q.r--;
            if(!q1[pa(q.l,q.r)])
            push(q);
        }
        mu[1]=mu[n1--];
        down(1);
    }
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【Qt】2.3 使用Qt设计师来创建对话框

下一篇:A -- HDU 4585 Shaolin