N个盒子M个物品,求装满盒子的最多

Yangyang loves AC
题意:

给出Yangyang N天中每天达到happy 的最大值,他会从M个ACMer中得到happy值; 求他能最多达到happy的天数。

分析:
如果直接贪心显然有问题,所以我们需要换个姿势。 二分答案+贪心: 二分得到最多happy 天数,然后贪心,每次从M个ACMer中选最大的happy值,放到容量最大的盒子里,用优先队列每次维护最大容量的盒子。 算法时间复杂度为O(M*log(M)*log(N))

代码:
const int MAX=20005; int H[MAX]; int W[MAX]; int n,m; bool OK(int num) { priority_queue pQ; for(int i=0; i0)pQ.push(tt); } return pQ.empty(); } int binarySearch() { int L=0; int R=n; int cnt=0; while(L>1; if(OK(mid)) { L=mid+1; cnt=max(cnt,mid); } else R=mid-1; } return cnt; } int main() { /*#ifndef ONLINE_JUDGE intxt; outtxt; #endif // ONLINE_JUDGE*/ while(~scanf("%d%d",&n,&m)) { for(int i=0; i

    推荐阅读