Codeforces 1003D Coins and Queries 【性质】

2018/07/04 10:27
阅读数 0

知道做这道题需要性质,怎么入手?

我想的是输入保证了a[i]都是power of two,而不是任意的数,那么一定得从二的整次数幂入手解决问题。

想到如果一个b可以被拼出来,那么他就能被写成多个power of 2相加的形式;那么我们每次用最大的power of 2去拼这个b,然后power of 2再逐渐减小,如果能拼的出来的话那他一定是答案;那会不会出现原本拼的出来,但在这种策略下拼不出来的情况呢?(及不应该每次用最大的去拼b)不会,因为如果你能用其他的方式拼出b(而且有更大的power of 2可取但没取),那你一定可以用那些小点的power of 2拼出来这个大的power of 2

 

考场的时候我忽略了2^0=1,觉得如果b是基数那肯定拼不出来.....5555555555555

 

 1 #include<iostream>
 2 #include<map>
 3 using namespace std;
 4 
 5 int a[200005];
 6 map<int,int> m;
 7 
 8 int main(){
 9     int n,q; cin>>n>>q;
10     for(int i=1;i<=n;i++){
11         cin>>a[i];
12         m[ a[i] ]++;
13     }
14     
15     for(int i=1;i<=q;i++){
16         int b; cin>>b;
17         int count=0;
18         for(int j=29;j>=0;j--){//先用大的拼
19             if( b==0 ) break;
20             int num = (1<<j);
21             if( num>b || m[num]==0 ) continue;
22             int take =  min( m[num],b/num );
23             count+=take; b-=take*num;
24         }
25 
26         if(b>0) cout<<-1<<endl;
27         else cout<<count<<endl;
28     } 
29     
30     return 0;
31 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部