题目链接：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
using namespace std;
int n, p, d, m, k;
set 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 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[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() 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
