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