试题 算法提高 双十一抢购

 Lan   2020-03-28 20:15   441 人阅读  0 条评论
资源限制
时间限制: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。
import java.util.*;

public class 双十一抢购 {

	public static class goods {
		public int num;
		public double price;
		public int off;

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		double money = input.nextDouble();
		int Nums = input.nextInt();
		goods[] lists = new goods[Nums];
		for (int i = 0; i < lists.length; i++) {
			lists[i] = new goods();
			lists[i].price = input.nextDouble();
			lists[i].off = input.nextInt();
			lists[i].num = i + 1;
		}
		for (int i = 0; i < lists.length; i++) {
			for (int j = i; j < lists.length; j++) {
				if (lists[i].off * lists[i].price < lists[j].off * lists[j].price) {
					goods temp = lists[j];
					lists[j] = lists[i];
					lists[i] = temp;
				} else if (lists[i].off * lists[i].price == lists[j].off
						* lists[j].price) {
					if (lists[i].price > lists[j].price) {
						goods temp = lists[j];
						lists[j] = lists[i];
						lists[i] = temp;
					} else if (lists[i].price == lists[j].price) {
						if (lists[i].num > lists[j].num) {
							goods temp = lists[j];
							lists[j] = lists[i];
							lists[i] = temp;
						}
					}
				}
			}
		}
		List<Integer> result = new ArrayList<Integer>();
		int success =0;
		for (goods goods : lists) {
			double price =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 (Integer integer : result) {
				System.out.print(integer+" ");
			}
		}
		
	}
}

思路来源:generous~

本文地址:https://www.lanol.cn/post/91.html
版权声明:本文为原创文章,版权归 Lan 所有,欢迎分享本文,转载请保留出处!

 发表评论


表情

还没有留言,还不快点抢沙发?