2015 一中培訓 day 5，2015一中

又是一天的爆零！！！！！

原本第一題 很容易做 竟然優化過度

丟了答案

先貼上一題

1693: ksum

Time Limit

1000 ms

Memory Limit

524288 KBytes

Judge

Standard Judge

Solved

18

Submit

41

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);
    }
}