【CF1398】E. Two Types of Spells（set）

题目链接：https://codeforces.com/problemset/problem/1398/E

分析

不难发现，每次我们要让能被双倍使用的咒语尽量大，能被双倍使用的咒语数量就是1类咒语的数量。而能被双倍使用的咒语即是除了第一次使用的1类咒语外的所有咒语。
根据贪心的思想，第一次使用的1类咒语肯定是1类咒语种最小的，其他咒语根据大小排序之后选择最大的几个即可。
可以用set来维护，具体实现看代码。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define lson (k << 1)
#define rson (k << 1 | 1)const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const ll P = 1e9 + 7;int n, op, db, cnt;
set<int> s1, s2; //分别存储第1类咒语以及所有能被双倍使用的咒语
set<int>::iterator f;
ll suma, sumb;void check()
{
    while(cnt < db && f != s2.begin()){
    f--;cnt++;sumb += *f;}while(cnt > db){
    sumb -= *f;f++;cnt--;}
}void insert(int x)
{
    s2.insert(x);if(x > *f){
    sumb += x;cnt++;}check();
}void erase(int x)
{
    if(x == *f){
    cnt--;f++;sumb -= x;}else if(x > *f){
    cnt--;sumb -= x;}s2.erase(x);check();
}int main() {
    int x;s2.insert(INF);f = --s2.end();scanf("%d",&n);while(n--){
    scanf("%d%d",&op,&x);if(op == 1){
    if(x > 0){
    db++;suma += x;if(!s1.size()){
    s1.insert(x);}else{
    if(x > *s1.begin()){
    s1.insert(x);insert(x);}else{
    insert(*s1.begin());s1.insert(x);}}}else{
    x = -x;suma -= x;db--;if(x == *s1.begin()){
    s1.erase(x);if(s1.size()) erase(*s1.begin());}else{
    erase(x);s1.erase(x);}}}else{
    if(x > 0){
    suma += x;insert(x);}else{
    x = -x;suma -= x;erase(x);}}check();printf("%lld\n",suma + sumb);}return 0;
}