新疆21年省赛D题
题目描述
给出一个长度为$n$的正整数序列$A$和一个数字$k$(原题中为$w$)， 求前$k$大的子段和
数据范围
$1 \leq n \leq 10^5$
$1 \leq k \leq min( \frac{n \times (n - 1)}{2}, 10^5)$
$0 \leq A_i \leq 10^9$
题解
由于序列中的每个数都非负， 所以最大的子段肯定是$[1, n]$， 此后， 最大的可能是$[2, n], [1, n - 1]$中的一个， 更一般的， 我们的子段和从大到小一定是两端点从外向内拓展的
我们建立一个大根堆， 初始将$[1, n]$放进堆里， 此后， 每次取出堆顶$[l, r]$并判断$[l, r]$有没有被取出过， 如果没有， 把$[l + 1, r], [l, r - 1]$放进堆里
代码
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
| #include <iostream>
#include <cstdio>
#include <queue>
#include <map>
int n, k;
long long s[100005];
struct Itv
{
long long sum;
int l, r;
bool operator < (Itv tmp) const
{
return sum < tmp.sum;
}
};
std:: priority_queue<Itv> pq;
std:: map<std:: pair<int, int>, bool> mp;
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++)
{
int a;
scanf("%d", &a);
s[i] = s[i - 1] + a;
}
pq.push((Itv){s[n], 1, n});
while(k --)
{
Itv tmp = pq.top();
pq.pop();
if(mp[std:: make_pair(tmp.l, tmp.r)])
{
k ++;
continue;
}
else
mp[std:: make_pair(tmp.l, tmp.r)] = true;
if(tmp.r > tmp.l)
pq.push((Itv){s[tmp.r] - s[tmp.l], tmp.l + 1, tmp.r}), pq.push((Itv){s[tmp.r - 1] - s[tmp.l - 1], tmp.l, tmp.r - 1});
printf("%lld%c", tmp.sum, " \n"[k == 0]);
}
return 0;
}
|