「bsoj5156」数组 - 宽搜+堆/平衡树+k大查询 | Bill Yang's Blog

「bsoj5156」数组 - 宽搜+堆/平衡树+k大查询

题目大意

    Peter喜欢玩数组。NOIP这天,他从Jason手里得到了大小为$n$的一个正整数数组。
    Peter求出了这个数组的所有子段和,并将这$n(n+1)/2$个数降序排序,他想知道前$k$个数是什么。


题目分析

第一眼觉得和昨天的第一题类似,直接二分+双指针。
第二眼发现要输出前$k$大。。。

思路和选择困难症类似,考虑用堆维护所有方案,取出的前$k$大即为答案。

因为状态量太大,因此要用宽搜以一定顺序一个一个加入状态。
对于本题,我们可以从大到小加入状态,先加入区间$[1,n]$,再从左右两端缩减区间。

但是这样统计可以出现重复(有做法可以避开去重),可以用堆+MapSet解决掉这个问题。

注意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;
}
姥爷们赏瓶冰阔落吧~
0%