2024年华为杯广东工业大学程序设计竞赛 B.你是银狼（反悔贪心）

题目链接

B 你是银狼

思路：

发现其实只有房间 $1$ 有的选，房间 $2,3$ 都没得选，是一定要选的。房间 $2$ 回血有益还能房间通过数 $+1$，因此我们肯定会选。而对于一系列房间 $1$，在血量允许的前提下我们肯定只选掉血最少的房间。

当我们到后面想选某个 $1,3$ 房间时，如果血量不够了，我们就想要之前选的若干个房间 $1$ 从选变成不选，如果当时没选的话，现在的血量就会变多，有可能就能选上这个房间了。所以我们可以用一个大根堆来存储一下之前选取的房间 $1$，尝试选上这个房间，如果血量不够了就尝试不选前面的若干个房间。也就是一个反悔贪心的思路。

code：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;ll n,M,S;
int a[maxn],x[maxn];int solve(){int ans=0,res=0;priority_queue<int> h;for(int i=1;i<=n;i++){if(x[i]==1){h.push(a[i]);M-=a[i];S-=a[i];res++;while(M<0 || S<0){int t=h.top();M+=t;S+=t;h.pop();res--;}}else if(x[i]==2){res++;M+=a[i];}else {M-=a[i];S-=a[i];while(!h.empty() && (M<0 || S<0)){int t=h.top();M+=t;S+=t;h.pop();res--;}if(M>=0 && S>=0)res++;//通关 else return ans;//似了 }ans=max(ans,res);}return ans;
}int main(){cin>>n>>M>>S;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>x[i];cout<<solve();return 0;
}