codeforces每日两道思维题(第 五 天)
2023-12-19 23:08:00
C. Game with Multiset
rating :未知
题意描述:
在这个问题中,最初会给你一个空的多集。您必须处理两种类型的查询:
在这个问题中,最初会给你一个空的多集。您必须处理两种类型的查询:
- ADD x - 在多集合中添加一个等于 2^x 的元素;
- GET w - 询问是否可以取当前多集的某个子集之和,并得到等于 w 的值。
解题思路:贪心策略,每次从最后往前开始找,只要能减就减掉,总共29个数字
完整代码:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>cnt(30,0);
while(n--){
int t,v;
cin>>t>>v;
if(t==1){
cnt[v]++;
}
else{
// 贪心策略 从大到小,将尽可能大的都删掉,剩下的小的开始穿插补齐
for(int i=29;i>=0;i--){
//这里的cnt[i]代表当前i有几个
//如果cnt太多,那么我们肯定不会删掉cnt,我们只需要删掉对应数量的i就行
//就用当前的v>>i
//只有当cnt[i] 大于 v>>i 才会用v
v-=min(v>>i,cnt[i])<<i;
// if((v>>i)>=cnt[i])v-=(cnt[i]<<i);
}
if(v<=0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
}
}
文章来源:https://blog.csdn.net/m0_74036487/article/details/135093607
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!