新疆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; }
|