资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 一年一度的双十一又来了，某网购网站又开始了半价销售的活动。 小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. 样例输入 10 3 5 0 4 0 10 1 样例输出 2 3 样例输入 10 3 11 0 21 1 100 1 样例输出 0 数据规模和约定 0<S<=10000,0<N<=1000,每一个a和b满足0<a<=1000且b=0或1。
解题思路： 该题的相对合理的方法是结构体，通过判别结构体内的属性然后进行判断，最后得到最终结果，思路简单，但是如果换成是二维数组那么解法相同，但是代码量复杂，且难以分辨，我第一次用的是二维数组，最终因为过多判断而失败，第二个方法是用结构体，参考了别人的代码，非常轻松实现，二次的代码如下：
#include<bits/stdc++.h> using namespace std; int a[1000][3]; int b[1000]; int main(){ int s, n; cin >> s >> n; for (int i = 0; i < n; i ++){ cin >> a[i][0] >> a[i][1]; a[i][2] = i + 1; } for(int i = 0; i < n - 1; i ++){ for (int j = 0; j < n - i - 1; j ++){ int temp1 = a[j][0]; int temp2 = a[j][1]; int temp3 = a[j][2]; if(a[j][1] == 1 && a[j + 1][1] == 0){ continue; }else if(a[j][1] == 0 && a[j + 1][1] == 0){ if(a[j][0] <= a[j + 1][0]){ continue; }else{ a[j][0] = a[j + 1][0]; a[j][1] = a[j + 1][1]; a[j][2] = a[j + 1][2]; a[j + 1][0] = temp1; a[j + 1][1] = temp2; a[j + 1][2] = temp3; } }else if(a[j][1] == 0 && a[j + 1][1] == 1){ a[j][0] = a[j + 1][0]; a[j][1] = a[j + 1][1]; a[j][2] = a[j + 1][2]; a[j + 1][0] = temp1; a[j + 1][1] = temp2; a[j + 1][2] = temp3; }else{ if(a[j][0] <= a[j + 1][0]){ continue; }else{ a[j][0] = a[j + 1][0]; a[j][1] = a[j + 1][1]; a[j][2] = a[j + 1][2]; a[j + 1][0] = temp1; a[j + 1][1] = temp2; a[j + 1][2] = temp3; } } } } int count = 0; int index = 0; for(int i = 0; i < n; i ++){ if(a[i][1] == 0 && count + a[i][0] <= s){ b[index ++] = a[i][2]; count += a[i][0]; }else if(a[i][1] == 1 && count + a[i][0] * 0.5 <= s){ b[index ++] = a[i][2]; count += a[i][0] * 0.5; }else{ continue; } } if(index != 0){ for(int i = 0; i < index - 1; i ++){ for (int j = 0; j < index - i - 1; j ++){ int temp = b[j]; if(b[j] > b[j + 1]){ b[j] = b[j + 1]; b[j + 1] = temp; } } for(int i = 0; i < index; i ++){ cout << b[i] << " "; } } }else{ cout << "0"; } return 0; } #include<iostream> #include<cstring> #include<algorithm> using namespace std; int b[1005]; int cnt=1; typedef struct { float cost; int off; int num; }things; things a[1005]; int main() { memset(b,0,sizeof(b)); float s,n; cin>>s>>n; for(int i=1;i<=n;i++) { a[i].num=i; cin>>a[i].cost>>a[i].off; } for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { if(a[i].cost*a[i].off/2<a[j].cost*a[j].off/2)//判断条件1 { things temp; temp=a[i]; a[i]=a[j]; a[j]=temp; } else if(a[i].cost*a[i].off/2==a[j].cost*a[j].off/2) { if(a[i].cost>a[j].cost)//判断条件2 { things temp; temp=a[i]; a[i]=a[j]; a[j]=temp; } else if(a[i].cost==a[j].cost) { if(a[i].num>a[j].num)//判断条件3 { things temp; temp=a[i]; a[i]=a[j]; a[j]=temp; } } } } for(int i=1;i<=n;i++)//按照排序依次将买得起的物品买入，将买的物品的num存入数组b { if(a[i].off==0&&a[i].cost<=s) { s-=a[i].cost; b[cnt++]=a[i].num; } else if(a[i].off==1&&a[i].cost/2<=s) { s-=a[i].cost/2; b[cnt++]=a[i].num; } } if(cnt==1)//一样都买不起输出0 printf("%d",0); sort(b,b+cnt); for(int i=1;i<cnt;i++) { printf("%d ",b[i]); } }参考的代码地址：https://blog.csdn.net/aqdk1/article/details/103984719
