[算法刷题] 试题 算法提高 双十一抢购

资源限制时间限制：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。

importjava.util.*;

publicclass双十一抢购{

	publicstaticclassgoods{
		publicintnum;
		publicdoubleprice;
		publicintoff;

	}

	publicstaticvoidmain(String[]args){
		//TODOAuto-generatedmethodstub
		Scannerinput=newScanner(System.in);
		doublemoney=input.nextDouble();
		intNums=input.nextInt();
		goods[]lists=newgoods[Nums];
		for(inti=0;i<lists.length;i++){
			lists[i]=newgoods();
			lists[i].price=input.nextDouble();
			lists[i].off=input.nextInt();
			lists[i].num=i+1;
		}
		for(inti=0;i<lists.length;i++){
			for(intj=i;j<lists.length;j++){
				if(lists[i].off*lists[i].price<lists[j].off*lists[j].price){
					goodstemp=lists[j];
					lists[j]=lists[i];
					lists[i]=temp;
				}elseif(lists[i].off*lists[i].price==lists[j].off
						*lists[j].price){
					if(lists[i].price>lists[j].price){
						goodstemp=lists[j];
						lists[j]=lists[i];
						lists[i]=temp;
					}elseif(lists[i].price==lists[j].price){
						if(lists[i].num>lists[j].num){
							goodstemp=lists[j];
							lists[j]=lists[i];
							lists[i]=temp;
						}
					}
				}
			}
		}
		List<Integer>result=newArrayList<Integer>();
		intsuccess=0;
		for(goodsgoods:lists){
			doubleprice=goods.price-goods.off*0.5*goods.price;
			if(price<=money){
				money-=price;
				success++;
				result.add(goods.num);
			}
		}
		if(success==0){
			System.out.println("0");
		}else{
			Collections.sort(result);
			for(Integerinteger:result){
				System.out.print(integer+"");
			}
		}
		
	}
}

思路来源：generous~