问题 A: 桐桐的贸易
时间限制: 1 Sec 内存限制: 64 MB
提交: 15 解决: 2
[提交][状态][讨论版]
题目描述
桐桐家在Allianceance城，好友ROBIN家在Horde城，假期，ROBIN邀桐桐去Horde城旅游。聪明的桐桐发现，A11iance城与Horde城的市场上的某些商品存在着很大的差价。可以从中获取相当可观的利润。为了赚回这次旅游的花费，桐桐决定在Alliance城购买一些商品，到Horde城以当地市场价卖掉，然后在Horde城买一些商品，再回到Alliance城卖掉。这样一个来回，桐桐可以赚到不少钱。
通过商业调查，他已经在出发前就知道了Alliance城和Horde城的各种商品的价格。在他现有的资产的前提下，他希望能够在一次旅行中赚取尽可能多的金币。那么请你设计一个程序，为桐桐设计一个购买方案，使一次来回能够赚到最多的金币。
输入
第1行，两个整数N、M(1≤N≤100000;1≤M≤100)，表示他在出发前有N个金币，Allian和Horde的市场中都有M种商品。
第2～M+l行，每行两个整数Ai、Bi，表示第i种商品在Alliance城的市场价为Ai，在市场价为Bi。
输出
第1行，一个整数，桐桐一次来回最多能够赚到的金币数。最后结果不超过4000000。
第2―M+l行，第i+l行为第i个商品的购买方法，输出一个句子。如果要从Alliance购买k个，输出“Buy k from Alliance”，如果要从Horde购买k个，输出“Buy k from Horde”，如果不需要购买，输出“Buy 0"。如果多个的方案赚得的金币都是最大，则输出购买的商品序号最靠前的这种方案。
样例输入
23 5
6 9
11 7
3 2
4 6
5 3
样例输出
33
Buy 3 from Alliance
Buy 1 from Horde
Buy 0
Buy 1 from Alliance
Buy 9 from Horde
提示
初始时，桐桐在A11iance城，他有23个金币，这时他购买3个商品1，1个商品4，花费3×6+1×4=22个金币，剩余1个金币。到达Horde城，他把它们卖掉，可以获得3×9+1×6=33个金币，赚了11个金币。这时，他用他的34个金币，在Horde城购买1个商品2，9个商品5，花费l×7+9×3=34个金币。回到Alliance城，卖掉可以获得1×11+9×5=56个金币，赚了22个金币。与起始时他的23个金币相比，他赚了33个金币。
没改对。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; typedef struct node{
int a;
int b;
int c;
};
node no[]; int cmp(int a,int b){
return no[a].b-no[a].a>no[b].b-no[b].a;
} int main()
{
int n;
int m;
int l=;
int p=;
int aa[];
int shifou_aa[]={};
int bb[];
int shifou_bb[]={};
int k=;
int sum1=;
int sum2=;
int sum=;
scanf("%d %d",&n,&m);
for(int i=;i<m;i++){
scanf("%d %d",&no[i].a,&no[i].b);
if(no[i].a<no[i].b){
no[i].c=;
}else{
no[i].c=;
}
}
for(int i=;i<m;i++){
if(no[i].c==){
for(int j=;j<n/no[i].a;j++){
aa[k++]=i;
}
}
}
sort(aa,aa+k-,cmp);
for(int i=;i<k;i++){
l+=no[aa[i]].a;
shifou_aa[i]=;
if(l<=n){
p=i;
}else{
l-=no[aa[i]].a;
shifou_aa[i]=;
continue;
}
}
for(int i=;i<=p;i++){
if(shifou_aa[i]==){
sum1+=no[aa[i]].b-no[aa[i]].a;
} }
sum=n;
n+=sum1; for(int i=;i<m;i++){
int temp=no[i].a;
no[i].a=no[i].b;
no[i].b=temp;
} ////////////////
l=;
for(int i=;i<m;i++){
if(no[i].c==){
for(int j=;j<n/no[i].a;j++){
bb[k++]=i;
}
}
}
sort(aa,aa+k-,cmp);
for(int i=;i<k;i++){
l+=no[bb[i]].a;
shifou_bb[i]=;
if(l<=n){
p=i;
}else{
l-=no[bb[i]].a;
shifou_bb[i]=;
continue;
}
}
for(int i=;i<=p;i++){
if(shifou_bb[i]==){
sum2+=no[bb[i]].b-no[bb[i]].a;
} }
int sss=sum1+sum2;
printf("%d %d %d",sum1,sum2,sss);
return ;
}