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