CF1003D Coins and Queries 贪心

Coins and Queries

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp has nn coins, the value of the ii-th coin is aiai. It is guaranteed that all the values are integer powers of 22 (i.e. ai=2dai=2d for somenon-negative integer number dd).

Polycarp wants to know answers on qq queries. The jj-th query is described as integer number bjbj. The answer to the query is the minimum number of coins that is necessary to obtain the value bjbj using some subset of coins (Polycarp can use only coins he has). If Polycarp can't obtain the value bjbj, the answer to the jj-th query is -1.

The queries are independent (the answer on the query doesn't affect Polycarp's coins).

Input

The first line of the input contains two integers nn and qq (1≤n,q≤2⋅1051≤n,q≤2⋅105) — the number of coins and the number of queries.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an — values of coins (1≤ai≤2⋅1091≤ai≤2⋅109). It is guaranteed that all aiai are integer powers of 22 (i.e. ai=2dai=2d for some non-negative integer number dd).

The next qq lines contain one integer each. The jj-th line contains one integer bjbj — the value of the jj-th query (1≤bj≤1091≤bj≤109).

Output

Print qq integers ansjansj. The jj-th integer must be equal to the answer on the jj-th query. If Polycarp can't obtain the value bjbj the answer to the jj-th query is -1.

Example

input

Copy

output

Copy

1
-1
3
2

题意： 给你n个硬币，每个硬币的价值是2的幂数，然后接下来有m次查询，每次查询问这个数值最少需要多少枚硬币能凑出来？

分析： 我们直接从可能的最大的2的幂数开始枚举，遇到比数值小的就加上，注意每种硬币肯恩有多个，我们加的时候得看所需要加的个数。经过分析可以知道我们要加的是这种硬币的个数和数值所需要的最多这种硬币个数的最小值

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 2e5 + ;

const int mod = 1e9 + ;

typedef long long ll;

int main() {

    ll n, m;

    while( cin >> n >> m ) {

        map<ll,ll> mm;

        for( ll i = ; i < n; i ++ ) {

            ll a;

            cin >> a;

            mm[a] ++;

        }

        while( m -- ) {

            ll t;

            cin >> t;

            ll ans = ;

            for( ll i = <<; i >= ; i /=  ) {

                ans += min( mm[i], t/i );

                t -= min( mm[i], t/i ) * i;

            }

            if( t ) {

                cout << - << endl;

            } else {

                cout << ans << endl;

            }

        }

    }

    return ;

}

巴特西

CF1003D Coins and Queries 贪心

最新文章

热门文章