专栏文章
题解：P11328 [NOISG 2022 Finals] Gym Badges
P11328题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minoehby
- 此快照首次捕获于
- 2025/12/02 05:43 3 个月前
- 此快照最后确认于
- 2025/12/02 05:43 3 个月前
-
主要算法：贪心、堆（优先队列）。
-
分析：
P11328 [NOISG 2022 Finals] Gym Badges题目的条件可以转化为：如果你参加这个比赛，让自己的等级提升 并获得一个徽章后，你的等级小于等于 ，那么你可以参加这个比赛。
所以，先对 从小到大排序。然后顺序遍历选比赛，如果可以选则选，否则一定要放弃一个比赛，由于每个比赛的贡献相同，那我们就放弃 最大的那个比赛。这个过程可以用一个大根堆（优先队列）来维护。
参考代码
CPP//Author: mairuisheng
//#pragma GCC optimize(3)
#include<cstdio>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;
char s;
s=getchar();
while(s<48||s>57)
{
if(s=='-')f=-f;
s=getchar();
}
while(s>47&&s<58)
{
x=(x<<3)+(x<<1)+s-48;
s=getchar();
}
return x*f;
}
constexpr int N=5e5+1;
struct Node
{
int tim,lim;
}a[N];
int n;
int ans;
priority_queue<int> q;
bool Cmp(Node x,Node y)
{
return x.lim<y.lim;
}
void Solve()
{
sort(a+1,a+1+n,Cmp);
int i,sum=0;
for(i=1;i<=n;++i)
{
q.push(a[i].tim);
sum+=a[i].tim;
if(sum<=a[i].lim)++ans;
else
{
sum-=q.top();
q.pop();
}
}
}
signed main()
{
n=read();
int i;
for(i=1;i<=n;++i)a[i].tim=read();
for(i=1;i<=n;++i)a[i].lim=read()+a[i].tim;
Solve();
printf("%lld",ans);
return 0;
}
- 更多练习题：
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...