题目链接: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;
}