题目描述
翰翰18岁生日的时候,达达给她看了一个神奇的序列 A1,A2,…,AN。
她被允许从中选择不超过 M 个连续的部分作为自己的生日礼物。
翰翰想要知道选择元素之和的最大值。
你能帮助她吗?
样例
输入样例:
5 2
2 -3 2 -1 2
输出样例:
5
算法1
(贪心 + 双链表 + 二叉堆) 思路
题意:选择至多m个段落,使得总和最大。
1.可以将段落合并成连续的正段和连续的负段。(因为在选择的时候,包含正数的话,选择左右两边连续的正数,能够使得结果变得更大。选择负数段的话,直接将连续的负数段抛弃,也能使得结果更大)
考虑如何将该题转化为Acwing147. 数据备份
如果当前要选择的cnt
(题目要求的选择段落数) 不足 m
(序列中总共m段连续正的),那么全选正的就能达到最大
cnt
> m
,那么所有的正段会选择,我们也要去掉k = cnt - m
段,即选择k = cnt - m
段,这k
段的和最小,删掉,即可。
发现Acwing147. 数据备份也是求最小,这题也是求最小,已经有点接近了。
分析去掉1段的话,该如何去。
1.如果最小的段落只选择了1个正段,我们可以直接抛弃它,将cnt - 1
, 并且假设cnt
总和为S,该段正数和为a[i]
, S - a[i]
2.如果选择了多个正段, ,S - |a[i] | - |a[i]|
, cnt - 2
。
证明两题等价
首先证明 这题可以转化为Acwing147. 数据备份
该题的选择方法能够转化为选择两两不相邻的线段。
1.如果当前选择段是正的,那么下一次的选择必定的隔着一段负段的正段
2.如果当前选择的段是连续的一段,那么去掉的负数段,必定也是间隔的。
如果选择负段的话,那么必定会选择两段间隔负数段,按照贪心,会使得结果变得更好。
最后证明Acwing147. 数据备份
选择方法可以转化为该题的选择方法
按照147题目的选择方法,肯定是间隔一个段落选择。
如果间隔的三段是正的,那么可以单独去掉。
如果间隔三段是负数的,那么相当于该题中选择[正,负,正,负,正,负,正],然后将其中负数段去掉。
具体做法
n个数据中,取最多m片数据(每片不相邻),总和最大。
几个明显特点:0可以忽略,符号相同的相邻数可以归并为一个数。
首先取得所有正数之和,
如果正数不多于m个,直接取这些正数即可,如果多取则取的是负数,只会减值,没必要。
如果正数超过m个,则删除一些正数,或者将一些不相邻的正数合并(让正数之间的负数生效选上即可)。
如果删除一些正数,肯定是删除的正数要越小越好,
如果让某个负数生效,则该负数的绝对值也是越小越好,
综上两条,肯定是选择绝对值越小越好。
将所有数的绝对值和原始编号加入优先队列pq,
如果删除了正数(总和去掉该值;总片数减少1),其两边是负数,
将来也有可能将这三个数合起来,连接再外一层两边的正数,
所以要把删掉的正数及其两边的负数合起来重新放入优先队列pq被后续选择。
如果删除了当前绝对值最小的负数(总和添加该负值,其实就是减去该数的绝对值;因为连接了本来不相邻的两片,所以总片数少1),
这个负数连接的两边的正数合并成了一片,这个新的整片数(三段之和:正负正)合起来重新放入优先队列pq被后续选择。
这两条都是对绝对值选最小的先选,然后总和减去该绝对值,该位置加上两边数重新放入pq,同时,删除左右结点。
依次循环至保留片数不超过m即可,总和就是答案。
经常要问结点的左右结点是谁,并且随时需要删除结点,所以需要使用双向链表保存。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int n, m;
int a[N], l[N], r[N];
bool st[N];
void remove(int p){
r[l[p]] = r[p];
l[r[p]] = l[p];
st[p] = true;
}
int main(){
cin >> n >> m;
int k = 0;
for (int i = 0; i < n; i ++){
int x;
cin >> x;
if (!x) continue;
if (!k || a[k] * x < 0) a[++ k] = x;//如果当前数和前一个数符号相反,说明不是连续段
else a[k] += x;//连续段继续加
}
n = k;
priority_queue<PII, vector<PII>, greater<PII>> heap;
int cnt = 0, res = 0;
for (int i = 1; i <= n; i ++)
if (a[i] > 0){//先加上正的
cnt ++;
res += a[i];
}
for (int i = 1; i <= n; i ++){
l[i] = i - 1;
r[i] = i + 1;
heap.push({abs(a[i]), i});//往堆里加所有数的绝对值
}
while (cnt > m){//堆里正的数 > m的时候,需要删除一些数。
while (st[heap.top().second]) heap.pop();//先将已经标记为true(即已经标记为删除的数)从堆中删除
auto t = heap.top();//取出最小的数
heap.pop();
int v = t.first, p = t.second;
if (l[p] != 0 && r[p] != n + 1 || a[p] > 0){//如果当前段落是正的,那么直接去掉
res -= v;
cnt --;
//去掉的时候需要考虑左右两边段,也需要加入到heap中,因为可能在后续的段落中去掉多个间隔负数段,
int left = l[p], right = r[p];
a[p] += a[left] + a[right];
heap.push({abs(a[p]), p});
remove(left);
remove(right);
}
}
cout << res << endl;
return 0;
}
晕了
OrzOrzOrzOrz