SRM 657 DIV1 Easy - ProblemSets x
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13771&rd=16417
・問題Easy,EM,Middle,MH,Hardの数が与えられる。
・ここから問題のセットをできるだけ多く作りたい。
・各問題セットは、Easy,Middle,Hardの問題を各一つ含む必要がある。
・問題EMはEasyもしくはMiddleの代わり、MHはMiddleもしくはHardの代わりに使える。
・このとき、作ることのできる最大の問題セット数を求める。
解き方
まずは法則がないか考えてしまうが、かなり複雑になりそう。
ここで作ることの問題セットがわかっていれば、それを作ることができるかどうかは
すぐに判定することができる。
よって二分探索を用いればよい。
コード
class ProblemSets {
public:
bool ispossible(long long x,long long E, long long EM, long long M, long long MH, long long H){
if(EM<x-E)return false;
if(MH<x-H)return false;
if(E<x)EM-=(x-E);
if(H<x)MH-=(x-H);
return M+EM+MH>=x;
}
long long maxSets(long long E, long long EM, long long M, long long MH, long long H) {
long long low=0,high=LONG_MAX;
while(high-low>1){
long long mid=(low+high)/2;
if(ispossible(mid,E,EM,M,MH,H))low=mid;
else high=mid;
}
return low;
}
};
public:
bool ispossible(long long x,long long E, long long EM, long long M, long long MH, long long H){
if(EM<x-E)return false;
if(MH<x-H)return false;
if(E<x)EM-=(x-E);
if(H<x)MH-=(x-H);
return M+EM+MH>=x;
}
long long maxSets(long long E, long long EM, long long M, long long MH, long long H) {
long long low=0,high=LONG_MAX;
while(high-low>1){
long long mid=(low+high)/2;
if(ispossible(mid,E,EM,M,MH,H))low=mid;
else high=mid;
}
return low;
}
};
