2f7f2e7e-2009-424e-a824-a590d1cd8234
[题目翻译]
问题陈述
高桥将踏上冒险之旅。
在探险过程中，会发生 \(N\) 个事件。\(i\)-th 事件 \((1\leq i\leq N)\) 由一对整数 \((t _ i,x _ i)\) 表示。\((1\leq t _ i\leq 2,1\leq x _ i\leq N)\) 并如下所示：
- 如果 \(t _ i=1\)，他找到了一个 \(x _ i\) 类型的药水。他可以选择捡起或丢弃。
- 如果是 \(t _ i=2\)，他将遇到一只 \(x _ i\) 类型的怪物。如果他有\(x _ i\)型药水，他可以使用一种药水击败怪物。如果他没有打败怪物，他就会被打败。
判断他是否可以打败所有怪物而不被打败。
如果他无法打败所有怪物，则打印 -1。
否则，让\(K\)成为他在冒险过程中拥有的最大药水数量。让 \(K _ {\min}\) 成为 \(K\) 在所有策略中不会被击败的最小值。打印 \(K _ {\min}\) 的值以及高桥实现 \(K _ {\min}\) 的行动。
[思路]:
有一个贪心策略：每次选在当前怪物前且距离最短的未被使用过的同种药水一定最优。
考虑感性证明：
如果选第一个出现的同种药水，则这个药水可能会让他一直拿着药水而不用，会使在单位时间里所拥有的最大数量增加。
因为下标本身就有单调性，所以直接用栈维护每种药水出现的位置即可，遇到怪物取出同种药水栈顶就代表取走这个位置的药水，用数组存下来最终最大数量模拟一遍就好啦。
考场我急了，所以吗，码风奇丑且用的大根堆，后来才发现下标本身就有单调性。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int n,t[N],a[N];
int ans[N],s[N],vis[N],sum,p;
priority_queue<int> q[N];
signed main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> t[i] >> a[i];
if(t[i]==1) q[a[i]].push(i);
else{
if(q[a[i]].empty()){//空了就代表在这个怪物前没有能杀死这个怪物的药水了。
puts("-1");
return 0;
}
ans[q[a[i]].top()]=1;
q[a[i]].pop();
}
}
for(int i=1;i<=n;i++){
if(ans[i]==1) vis[a[i]]++,sum++;
if(t[i]==2){
vis[a[i]]--,sum--;
}
p=max(p,sum);
}
cout << p << "\n";
for(int i=1;i<=n;i++){
if(t[i]==2) continue;
cout << ans[i] << ' ';
}
return 0;
}