TopCoder SRM 380 Div1 Medium CompilingDecksWithJokers

問題

n種類のカードがそれぞれcards[i]枚と、jokers枚のジョーカーがある。
これらを使って、
それぞれのカードが一種類一枚ずつ、あるいは、
それぞれのカードがどれか一種類以外一枚ずつと、ジョーカー一枚のデッキをできるだけ多く作りたい。

デッキは最大でいくつできるか求めよ。

制約条件

n≦50
cards[i]≦500000000
jokers≦500000000

方針

m枚のデッキが作れるかどうかについて二分探索。
m枚を決めると、同じデッキにはジョーカーは2枚以上入れられないので、
現時点で使えるジョーカーの枚数が決まる。

ジョーカーでないカードが使える場合はgreedyにそのカードを使えばよく、
ジョーカーを使ったら、ジョーカーを使える枚数から使った分だけ引く。

ソースコード

class CompilingDecksWithJokers {
	public:
	int maxCompleteDecks(vector <int> cards, int jokers) 
	{
		ll lo=0,hi=1ll<<40,mid;
		int n=cards.size();
		while(lo+1<hi){
			mid=(lo+hi)/2;
			ll can=mid, use=0;
			rep(i,n){
				if(cards[i]<mid){
					can-=mid-cards[i];
					use+=mid-cards[i];
				}
			}
			if(can>=0&&use<=jokers)lo=mid; else hi=mid;
		}
		return lo;
	}
};