問題
http://community.topcoder.com/stat?c=problem_statement&pm=8440&rd=10800
解き方
一見すべての価格について調べる必要があり、10^6なのでそれでも解けそう。
ただし少し考えると各顧客の最大購入価格が一番利益を得ることができる選び方なので
すべての最大購入価格のうち、最も利益の出るものが答えになる。
コード
class SellingProducts {
public: int optimalPrice(vector<int> price, vector<int> cost) {
int n=price.size();
int profit=0,idx=0;
FORE(i,0,n){
int cur=0;
FORE(j,0,n)if(price[i]<=price[j] && price[i]>cost[j]){
cur+=price[i]-cost[j];
}
if(cur>=0 && (profit<cur || (profit==cur && price[idx]>price[i]) )){
profit=cur;
idx=i;
}
}
return profit==0 ? 0 : price[idx];
}
};
public: int optimalPrice(vector<int> price, vector<int> cost) {
int n=price.size();
int profit=0,idx=0;
FORE(i,0,n){
int cur=0;
FORE(j,0,n)if(price[i]<=price[j] && price[i]>cost[j]){
cur+=price[i]-cost[j];
}
if(cur>=0 && (profit<cur || (profit==cur && price[idx]>price[i]) )){
profit=cur;
idx=i;
}
}
return profit==0 ? 0 : price[idx];
}
};