問題
http://community.topcoder.com/stat?c=problem_statement&pm=12948&rd=15838
・様々なハンバーガーがあり、そのタイプと大きさが与えられる。
・好きなだけハンバーガーを選んでよく、選んだ後のスコアは選んだタイプの種類×大きさの和
となる。
・このとき、取りうる最大のスコアを求める。
解き方
・大きさがマイナスになるときは判定が必要になる
・とりあえず、大きさが０以上の時はスコアが下がることはないので必ず選ぶ
・ソートして、大きい順に判定
・大きさが０以上のときは必ず選び、マイナスのときはそのハンバーガーを選んだときにスコアが上がれば選び、そうでなければ選ばないのが最適解になりそう
・あるハンバーガーを選ばないとき、それより小さい大きさのときはスコアはそれ以上にならないので貪欲法で解ける
→System Passed
コード
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 AlienAndHamburgers {
public: int getNumber(vector<int> type, vector<int> taste) {
int n=type.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(taste[i],type[i]));
sort(p.rbegin(),p.rend());
int used[101]={};
int ret=0,cnt=0;
FORE(i,0,n){
if(p[i].first>=0 || ret*cnt<(ret+p[i].first)*(cnt+(used[p[i].second]==0))){
ret+=p[i].first;
cnt+=(used[p[i].second]==0);
used[p[i].second]=1;
}
}
return ret*cnt;
}
};
#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 AlienAndHamburgers {
public: int getNumber(vector<int> type, vector<int> taste) {
int n=type.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(taste[i],type[i]));
sort(p.rbegin(),p.rend());
int used[101]={};
int ret=0,cnt=0;
FORE(i,0,n){
if(p[i].first>=0 || ret*cnt<(ret+p[i].first)*(cnt+(used[p[i].second]==0))){
ret+=p[i].first;
cnt+=(used[p[i].second]==0);
used[p[i].second]=1;
}
}
return ret*cnt;
}
};