SRM576 Div2 Easy "TheExperimentDiv2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12508
訳
スポンジがどれほど水分を含んでいるのか計測を行った。
この実験が行われた部屋は側面が密閉されているため、2次元として考える事が出来る。
この部屋は幅がNセンチメートルあり、
天井にN個のドロップカウンター(雫を垂らす機械)が設置されている。
ドロップカウンター No.0 は部屋の左端から0.5センチの所に設置されており、
それから右側に1センチ間隔で No.N-1までのドロップカウンターが設置されている。
i番目のドロップカウンターは1分間にintensity[i] 回、雫を垂らす。
この部屋にはM個のスポンジも設置されている。
i番目(最初は0)のスポンジは天井からi+1センチ下に水平に設置されており、
その左端は部屋の左の壁からleftEnd[i]センチ離れた位置にある。
全てのスポンジは長さがちょうどLセンチであり、厚さは無視できる程薄くなっている。
それぞれのスポンジはその場所に落ちてきた雫を完全に吸収する。
それぞれのスポンジが、1分間あたりどれほどの雫を吸収するのかを返せ。
制約
1 <= N <= 50
1 <= intensity[i] <= 1000
1 <= M <= 50
考えた事
上にあるスポンジを優先的に計算し、
既にスポンジに吸収されたドロップカウンターを
重複して計算しないようにする。
ソースコード
class TheExperimentDiv2 { public: vector <int> determineHumidity(vector <int> intensity, int L, vector <int> leftEnd){ bool use[55]; memset( use, false, sizeof(use) ); int n = leftEnd.size(); int m = intensity.size(); vector<int> res; for( int i = 0; i < n; i++ ){ res.push_back(0); for( int j = leftEnd[i]; j < m && j < leftEnd[i] + L; j++ ){ if( use[j] ) continue; res[i] += intensity[j]; use[j] = true; } } return res; } };