题目链接:https://codeforces.com/problemset/problem/1398/E
题目大意
你有一个集合,初始为空。
有两种类型的元素,一种是普通元素,一种是强化元素,两种元素都有一个数值。
有 \(n\) 次操作,每次操作会往集合中加入一个元素或者删除一个元素。
每次操作后,你都需要确定集合中元素的一个排列,使得排列的价值最大。
排列价值的计算规则是:
每个元素的价值就是它对应的数字,但是强化元素能够使它在排列中后一个位置的元素的价值翻倍(即:对于排列中某一个元素来说,如果它前一个位置的元素是一个强化元素,则这个元素的价值是它本身的数值 \(\times 2\))。
举个例子,假设现在有三个元素:
- 第 \(1\) 个元素是一个数值为 \(5\) 的普通元素;
- 第 \(2\) 个元素是一个数值为 \(1\) 的强化元素;
- 第 \(3\) 个元素是一个数值为 \(8\) 的强化元素。
则:
- 如果按照第 \(1\) 个元素,第 \(2\) 个元素,第 \(3\) 个元素排列,对应的价值为 \(5 + 1 + 2 \cdot 8 = 22\) ;
- 如果按照第 \(1\) 个元素,第 \(3\) 个元素,第 \(2\) 个元素排列,对应的价值为 \(5 + 8 + 2 \cdot 1 = 15\) ;
- 如果按照第 \(2\) 个元素,第 \(1\) 个元素,第 \(3\) 个元素排列,对应的价值为 \(1 + 2 \cdot 5 + 8 = 19\) ;
- 如果按照第 \(2\) 个元素,第 \(3\) 个元素,第 \(1\) 个元素排列,对应的价值为 \(1 + 2 \cdot 8 + 2 \cdot 5 = 27\) ;
- 如果按照第 \(3\) 个元素,第 \(1\) 个元素,第 \(2\) 个元素排列,对应的价值为 \(8 + 2 \cdot 5 + 1 = 19\) ;
- 如果按照第 \(3\) 个元素,第 \(2\) 个元素,第 \(1\) 个元素排列,对应的价值为 \(8 + 2 \cdot 1 + 2 \cdot 5 = 20\) 。
解题思路
假设任意次操作之后,集合中有 \(m\) 个普通元素,和 \(k\) 个强化元素。则:
- 若数值最大的 \(k\) 个元素 不全是 强化元素,则答案为:所有元素的数值和 + 数值最大的 \(k\) 个元素的数值和
- 若数值最大的 \(k\) 个元素 全是 强化元素,则答案为:所有元素的数值和 + 数值最大的 \(k-1\) 个元素(当然它们都是强化元素)的数值和 + 数值最大的 \(1\) 个非强化元素的数值
示例程序
实现时,用:
- \(st[0]\) 保存普通元素(\(m\) 对应普通元素个数);
- \(st[1]\) 保存强化元素(\(k\) 对应强化元素个数);
- \(st2[1]\) 保存数值最大的 \(k\) 个元素;
- \(st2[0]\) 保存除了数值最大的 \(k\) 个元素以外其余的元素;
- \(sum\) 对应 \(st2[1]\) 中数值最大的 \(k\) 个元素之和;
- \(sum2\) 对应目前所有元素之和
(命名比较随意,主要是因为写的时候发现少了又加了一个;包括 \(st2[0]\) 和 \(st2[1]\) 一开始我是开了两个堆,结果发现堆不支持随机删除囧)
#include <bits/stdc++.h>
using namespace std;
int n, p, d, m, k;
set<int> st[2], st2[2];
long long sum, sum2; // sum 记录前k大值之和,sum2 记录所有值之和
int main() {
scanf("%d", &n);
while (n--) {
scanf("%d%d", &p, &d);
if (d > 0) {
st[p].insert(d);
p ? k++ : m++;
st2[0].insert(d);
sum2 += d;
}
else { // d < 0
d = -d;
p ? k-- : m--;
st[p].erase(d);
if (st2[0].count(d)) st2[0].erase(d);
else {
st2[1].erase(d);
sum -= d;
}
sum2 -= d;
}
while (st2[0].size() && st2[1].size()) {
int x = *st2[0].rbegin();
int y = *st2[1].begin();
if (x > y) {
st2[0].erase(x);
st2[1].erase(y);
st2[0].insert(y);
st2[1].insert(x);
sum += x - y;
}
else
break;
}
while (st2[1].size() < k) {
assert(!st2[0].empty());
int x = *st2[0].rbegin();
st2[0].erase(x);
st2[1].insert(x);
sum += x;
}
while (st2[1].size() > k) {
assert(!st2[1].empty());
int x = *st2[1].begin();
st2[1].erase(x);
sum -= x;
st2[0].insert(x);
}
long long ans;
if (st[0].empty())
ans = sum2 + sum - (*st[1].begin());
else if (st[1].empty())
ans = sum2;
else if (*st[0].rbegin() < *st[1].begin())
ans = sum2 + sum - (*st[1].begin()) + (*st[0].rbegin());
else
ans = sum2 + sum;
printf("%lld\n", ans);
}
return 0;
}
标签:set,题解,sum,元素,Two,数值,st,st2,sum2
From: https://www.cnblogs.com/quanjun/p/17443454.html