http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11560&courseid=0
题意：总共有n天,每天yangyang都需要一个快乐值,有m个队友,每个队友都会给阳阳一个快乐值(为2的幂),并且只能给一次,如果某一天队友给的快乐值达到yangyang需要的快乐值那么这一天yangyang就是快乐的,统计最多快乐的天数。
思路：因为达到快乐的天数不要求连续,那么只要对需要的快乐值和队友给的快乐值分别排序,然后每次二分出一个快乐的天数x,判断能不能用m个数去满足它,所以把0到x的数加入优先队列,然后从m开始从大到小去覆盖优先队列的值.
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 using namespace std; 5 6 int n,m,h[20010],p[20010]; 7 8 bool ok(int x) 9 { 10 priority_queue<int>que; 11 for(int i=0;i<x;i++) 12 que.push(h[i]); 13 int y=m; 14 while(!que.empty()) 15 { 16 y--; 17 if(y<0) break; 18 if(p[y]<que.top()) que.push(que.top()-p[y]); 19 que.pop(); 20 } 21 return que.empty(); 22 } 23 void solve() 24 { 25 int lb=0,ub=n; 26 int cnt=0; 27 while(lb<=ub) 28 { 29 int mid=(lb+ub)>>1; 30 if(ok(mid)) 31 { 32 lb=mid+1; 33 cnt=max(cnt,mid); 34 // printf("%d %d ",cnt,lb); 35 } 36 else ub=mid-1; 37 } 38 printf("%d ",cnt); 39 } 40 int main() 41 { 42 //freopen("a.txt","r",stdin); 43 while(~scanf("%d%d",&n,&m)) 44 { 45 for(int i=0;i<n;i++) scanf("%d",&h[i]); 46 for(int i=0;i<m;i++) scanf("%d",&p[i]); 47 sort(h,h+n); 48 sort(p,p+m); 49 solve(); 50 } 51 return 0; 52 }