codeforces每日两道思维题(第 五 天)

2023-12-19 23:08:00

C. Game with Multiset

rating :未知

原题链接:Problem - C - Codeforces

题意描述:

在这个问题中,最初会给你一个空的多集。您必须处理两种类型的查询:

在这个问题中,最初会给你一个空的多集。您必须处理两种类型的查询:

  1. ADD x - 在多集合中添加一个等于 2^x 的元素;
  2. 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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。