SRM 608 DIV1 Easy - MysticAndCandies (復習×○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=12997&rd=15841

複数の箱それぞれに対しlowとhighの値が割り振られ、lowからhighの間の数のキャンディーが入っている。
また、合計のキャンディーの数もわかっている。

プレイヤーは複数の箱を選び、X個以上のキャンディーを食べたい。
このとき、どの箱を選んでもX個以上のキャンディーが入っているような、最小の箱の数を求める。

解き方


問題文のどのキャンディーの入り方でもX個以上、という最悪条件になっていることに気付くのに時間がかかってしまいました。

答えは最大で箱の数なので、選ぶ数は1~nまで順番に調べていき
条件を満たせばそこで答えになります。

条件の満たし方は以下の2通りのうちいずれかを満たせばよいです。
①最小のキャンディーは必ず入っているので、最小の数のみの和でX以上になること
②選んでいない残りの箱の最大数がC-X以下になること。

例外条件として、②は選んだ箱の取りうるキャンディー数がXを満たすか気になります。
これは、選んだ箱の取りうるキャンディー数がX未満の場合、残りの箱は最大数を選んでいるため合計のキャンディー数が決して満たない数になってしまいます。

①の例外条件として合計だけでは満たさなくとも、残りで最大を選んだときのバッファを足せば満たすかがありますが、これはまさに②なので大丈夫です。

例外条件をちゃんと確かめるか、もしくはコードでカバーしておくかが大事です。

コード


#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class MysticAndCandies {

public: int minBoxes(int C, int X, vector<int> low, vector<int> high) {
int n=low.size();

sort(low.rbegin(),low.rend());
sort(all(high));

int r1=0,s1=0;
while(r1<n&&s1<X){
s1+=low[r1];
r1++;
}

int r2=0,s2=0;
while(r2<n-1&&s2+high[r2]<=C-X){
s2+=high[r2];
r2++;
}

return min(r1,n-r2);
}

};
このエントリーをはてなブックマークに追加