算法提高 双十一抢购 C++

算法提高 双十一抢购 C++

题目

问题描述
　　一年一度的双十一又来了，某网购网站又开始了半价销售的活动。
　　小G打算在今年的双十一里尽情地购物，以享受购买的极度快感，她已经列好了她想买的物品的列表。
　　当然小G并不是出身富贵家庭，所以她网银里的钱只是一个有限的整数S（单位：元）。
　　这次抢购她打算遵循这三个原则选择每一个物品：
　　1.先买能“赚”最多的；
　　2.在“赚”一样多的情况下，先买最便宜的（这样买的东西就可能更多了）；
　　3.在前两条里都判断不了购买顺序的话，先购买在列表里靠前的。
　　（由于网站里还是有一部分商品并没有打五折，所以2的情况（“赚”的钱数为0）是完全可能发生的）
　　现在，在双十一的这一天，你要帮小G编写一个程序，来看看她应该去买她列表里的哪些物品。（总价格不要超过S哦）
　　要是帮她写好这个程序的话，或许你能在光棍节这一天里赢得她的芳心哦~
　　输入格式
　　输入共N+1行。
　　第一行包含两个整数S和N，S表示小G的可用金额，N表示她看上的物品个数。
　　接下来N行，对应每一个物品，每行有两个整数a和b，a是物品的原价（单位：元），b为0或1，若b为0，则此物品不半价，若b为1，则此物品半价销售。
　　输出格式
　　输出共一行，为小G要买的物品序号（从1开始），用空格隔开，注意按序号从小到大输出。
　　若小G一件都买不了，则输出0.

代码：

#include <iostream>
using namespace std;
/*typedef struct {int num;float price;int discount;
}thing;*/
struct thing{int num;float price;int discount;
};
int main(int argc, char *argv[]) {float s;int n;cin>>s>>n;/*thing a[n],b[n],t;*/struct thing a[n],b[n],t;int i,j,k=0;for(i=0;i<n;i++){cin>>a[i].price>>a[i].discount;a[i].num=i;		if(a[i].discount==1)a[i].price=a[i].price/2;}for(i=0;i<n-1;i++){for(j=0;j<n-1-i;j++){if(a[j].price<a[j+1].price){//将数组a按price的值从大到小排列 , t=a[j];a[j]=a[j+1];a[j+1]=t;}if(a[j].price==a[j+1].price){//一样的价格，先买列表里靠前的 ，条件3 if(a[j].num>a[j+1].num){t=a[j];a[j]=a[j+1];a[j+1]=t;}}}}for(i=0;i<n;i++){//按上面排好的顺序，从i=0开始，先买能“赚”最多的（discount==1），条件1 if(a[i].discount==1&&a[i].price<=s){s-=a[i].price;				b[k++]=a[i];	//先把满足条件1的存入数组b	}			}for(i=0;i<n-1;i++){for(j=0;j<n-1-i;j++){if(a[j].price>a[j+1].price){//将数组a按price的值重新从小到大排列 t=a[j];a[j]=a[j+1];a[j+1]=t;}}if(a[j].price==a[j+1].price){//一样的价格，先买列表里靠前的 ，条件3 if(a[j].num>a[j+1].num){t=a[j];a[j]=a[j+1];a[j+1]=t;}}}for(i=0;i<n;i++){//按上面排好的顺序，从i=0开始，在“赚”一样的情况下（discount==0），先买最便宜的 ，条件2 if(a[i].discount==0&&a[i].price<=s){s-=a[i].price;			b[k++]=a[i];//再把满足条件2的存入数组b}}if(k!=0){for(i=0;i<k-1;i++){for(j=0;j<k-1-i;j++){if(b[j].num>b[j+1].num){//将数组b按num值从小到大排列 ，条件3 t=b[j];b[j]=b[j+1];b[j+1]=t;}}}for(i=0;i<k;i++)cout<<b[i].num+1<<" ";cout<<endl;	}elsecout<<0<<endl;return 0;
}

若想更简洁，可参考