問題
http://community.topcoder.com/stat?c=problem_statement&pm=12296&rd=15182
解き方
貪欲法で解けば良い。システムテストで落ちないように間違いの少ないような実装を
するよう気をつける。
コード
class TomekPhone {
public: int minKeystrokes(vector<int> f, vector<int> key) {
int n=f.size();
int cnt=0;
FORE(i,0,key.size())cnt+=key[i];
if(n>cnt)return -1;
int ret=0,p=1;
while(1){
int finish=1;
FORE(i,0,n)if(f[i]!=0)finish=0;
if(finish)break;
sort(f.rbegin(),f.rend());
cnt=0;
FORE(i,0,key.size()){
if(key[i]>0)key[i]--,cnt++;
}
FORE(i,0,cnt)if(f[i%n]>0){
ret+=f[i%n]*p;
f[i%n]=0;
}
p++;
}
return ret;
}
};
public: int minKeystrokes(vector<int> f, vector<int> key) {
int n=f.size();
int cnt=0;
FORE(i,0,key.size())cnt+=key[i];
if(n>cnt)return -1;
int ret=0,p=1;
while(1){
int finish=1;
FORE(i,0,n)if(f[i]!=0)finish=0;
if(finish)break;
sort(f.rbegin(),f.rend());
cnt=0;
FORE(i,0,key.size()){
if(key[i]>0)key[i]--,cnt++;
}
FORE(i,0,cnt)if(f[i%n]>0){
ret+=f[i%n]*p;
f[i%n]=0;
}
p++;
}
return ret;
}
};