题目大意
Peter喜欢玩数组。NOIP这天，他从Jason手里得到了大小为$n$的一个正整数数组。
Peter求出了这个数组的所有子段和，并将这$n(n+1)/2$个数降序排序，他想知道前$k$个数是什么。
题目分析
第一眼觉得和昨天的第一题类似，直接二分+双指针。
第二眼发现要输出前$k$大。。。
思路和选择困难症类似，考虑用堆维护所有方案，取出的前$k$大即为答案。
因为状态量太大，因此要用宽搜以一定顺序一个一个加入状态。
对于本题，我们可以从大到小加入状态，先加入区间$[1,n]$，再从左右两端缩减区间。
但是这样统计可以出现重复（有做法可以避开去重），可以用堆+Map或Set解决掉这个问题。
注意Set的去重是基于小于符号的，因此必须要将$l,r$重载进去，至于如何重载？不是$==$即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
LL n,k,a[maxn],sum=0;
struct HeapNode {
int l,r;
LL val;
HeapNode(int _l=0,int _r=0,LL _v=0):l(_l),r(_r),val(_v) {}
bool operator < (const HeapNode& b) const {
return val<b.val||(val==b.val&&r<b.r)||(val==b.val&&r==b.r&&l>b.l);
}
};
set<HeapNode>S;
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
sum+=a[i];
}
S.insert(HeapNode(1,n,sum));
for(int i=1; i<=k; i++) {
HeapNode Now=*S.rbegin();
S.erase(Now);
printf("%lld ",Now.val);
if(Now.l<Now.r) {
HeapNode Next=Now;
Next.l++;
Next.val-=a[Now.l];
S.insert(Next);
Next=Now;
Next.r--;
Next.val-=a[Now.r];
S.insert(Next);
}
}
return 0;
}
|
