Codeforces Round #494 (Div. 3) D. Coins and Queries (贪心,数学)

题意:给你一组全是\(2^d\ (d\ge0)\)的数,询问q次,每次询问一个数,问这个数是否能够由原数组中的数相加得到,如果能,输出最少用多少个数,否则输出\(-1\).
题解:首先贪心得出结论:如果情况成立,那么最少的情况一定是优先用数组中大的数,然后我们用桶记录数组数的个数,从\(inf\)开始枚举,\(k\)表示桶中的数和\(x\)所需次数的最小值,最后如果\(x\ne 0\)那么条件不满足,否则输出\(ans\)即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

int n,q;

int x;

int ans;

map<int,int> mp;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n>>q;

     for(int i=1;i<=n;++i){

         cin>>x;

         mp[x]++;

     }

     while(q--){

         cin>>x;

         ans=0;

         for(int i=1<<30;i>=1;i/=2){

             int k=min(mp[i],x/i);

             ans+=k;

             x-=k*i;

         }

         if(x) puts("-1");

         else printf("%d\n",ans);

     }

    return 0;

}

巴特西

Codeforces Round #494 (Div. 3) D. Coins and Queries (贪心,数学)

最新文章

热门文章