問題
http://community.topcoder.com/stat?c=problem_statement&pm=1517&rd=4600
指定された数のハンバーガーを両面焼きたい。
両面焼くのには、片面ずつ、各５分必要となる。
また、フライパンが与えられ、一度に何枚のハンバーガーが焼けるかがわかっている。
このとき、指定された数のハンバーガーを焼くのに必要な最小時間を求める。
解き方
ハンバーガーの数は１０００なので全探索で解ける。
シミュレーション問題なので、いかにシンプルに解くか。
片面ずつの配列を作って埋めていってもよいが、それぞれを区別する必要はないので
以下のように整理する。
フライパン１回使用につき、
①まずは両面とも焼いていないものを優先して載せる
②あまったところで片面のみ焼いてあるものを載せる。
③最後に両面とも焼けていないもの、片面のみ焼けているものの数を更新し、どちらも０になるまでループさせる。
１回のターンにつき①と②で同じものを選ばないようにするのがSystemtestで落ちないためのポイント。
コード
class FryingHamburgers {
public: int howLong(int panSize, int hamburgers) {
int ret=0,half=0;
while(hamburgers+half>0){
ret++;
int first=min(hamburgers,panSize);
int both=min(panSize-first,half);
hamburgers-=first;
half+=first;
half-=both;
}
return ret*5;
}
};
public: int howLong(int panSize, int hamburgers) {
int ret=0,half=0;
while(hamburgers+half>0){
ret++;
int first=min(hamburgers,panSize);
int both=min(panSize-first,half);
hamburgers-=first;
half+=first;
half-=both;
}
return ret*5;
}
};
using namespace std;
#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 FryingHamburgers {
public: int howLong(int p, int h) {
if(h==0)return 0;
return p<=h ? (h*2+p-1)/p*5 : 10;
}
};
#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 FryingHamburgers {
public: int howLong(int p, int h) {
if(h==0)return 0;
return p<=h ? (h*2+p-1)/p*5 : 10;
}
};