問題
http://community.topcoder.com/stat?c=problem_statement&pm=8467&rd=12180
キャンドルが複数与えられ、それぞれの高さがわかっている。
１日目は１つ、2日めは２つ、、、とキャンドルをつけていき、
最大何日目までキャンドルをつけられるか求める。
ただし、つけられたキャンドルは１日につき高さが１減り、０となると消滅してしまう。
解き方
要素数が５０であることから最大値は５０になる。
よって、毎回ソートしてもO(50*50*50log50)=O(1.25*10^5log50)となり
貪欲法で全探索しても間に合う。
コード
class OlympicCandles {
public: int numberOfNights(vector<int> candles) {
int n=candles.size();
int turn=0;
while(turn<n){
sort(candles.rbegin(),candles.rend());
for(int i=0;i<turn+1;i++){
if(candles[i]<=0)return turn;
}
for(int i=0;i<turn+1;i++)candles[i]--;
turn++;
}
return turn;
}
};
public: int numberOfNights(vector<int> candles) {
int n=candles.size();
int turn=0;
while(turn<n){
sort(candles.rbegin(),candles.rend());
for(int i=0;i<turn+1;i++){
if(candles[i]<=0)return turn;
}
for(int i=0;i<turn+1;i++)candles[i]--;
turn++;
}
return turn;
}
};