2010 TCO Qualification Round 2 - JingleRingle
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10896&rd=14277
・１つの硬貨Jingleをある硬貨Ringleで売るsellerが複数人と、
１つの硬貨Jingleをある硬貨Ringleで買うbuyerが複数人いる。
また、buyerに売るときは売るときの硬貨floor(X*tax/100)の税金がかかる。
・１人のsellerからは１回、１人のbuyerからは１回の取引しかできないとき、
得られる最大のprofitを求める。
解き方
・貪欲法で解くことができそう。
・ソートし、一番安いsellerと一番高く売れるbuyerについて税金も含めて利益が出るときは取引し、そうでないときは取引しなければよい。
コード
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 JingleRingle {
public: int profit(vector<int> buyOffers, vector<int> sellOffers, int tax) {
int n=buyOffers.size();
int m=sellOffers.size();
if(n==0||m==0)return 0;
sort(all(buyOffers));
sort(all(sellOffers));
int ret=0;
int l=0,r=n-1;
while(l<m && r>=0){
double cost=floor(buyOffers[r]*tax/100.0);
if(buyOffers[r]-cost>sellOffers[l]){
ret+=buyOffers[r]-cost-sellOffers[l];
l++;
r--;
}
else break;
}
return ret;
}
};
#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 JingleRingle {
public: int profit(vector<int> buyOffers, vector<int> sellOffers, int tax) {
int n=buyOffers.size();
int m=sellOffers.size();
if(n==0||m==0)return 0;
sort(all(buyOffers));
sort(all(sellOffers));
int ret=0;
int l=0,r=n-1;
while(l<m && r>=0){
double cost=floor(buyOffers[r]*tax/100.0);
if(buyOffers[r]-cost>sellOffers[l]){
ret+=buyOffers[r]-cost-sellOffers[l];
l++;
r--;
}
else break;
}
return ret;
}
};
