Problem description
Once a year, double eleven came again, and an online shopping website started a half price sales activity.
Little G plans to go shopping on this year's double 11 to enjoy the extreme pleasure of buying. She has made a list of the items she wants to buy.
Of course, little G is not from a rich family, so her money in online banking is only a limited integer S (unit: yuan).
This time, she plans to follow these three principles to choose each item:
1. Those who can earn the most first;
2. In the case of "making" as much, buy the cheapest first (so that you can buy more things);
3. If you can't judge the purchase order in the first two items, first buy the one in the top of the list.
(as there are still some products in the website that do not have a 50% discount, the situation of 2 (the amount of money earned is 0) is completely possible.)
Now, on the day of double eleven, you need to help little G write a program to see what items she should buy from her list. (the total price should not exceed S)
If you help her write this program, maybe you can win her heart on singles day~
Input format
Enter a total of N+1 lines.
The first line contains two integers, S and N. S represents the available amount of small G, and N represents the number of items she likes.
Next N lines, corresponding to each item, each line has two integers a and b, a is the original price of the item (unit: yuan), b is 0 or 1, if b is 0, then the item is not half price, if b is 1, then the item is sold half price.
Output format
Output a total of one line, for small G to buy the item serial number (starting from 1), separated by spaces, pay attention to the serial number from small to large output.
If none of the small G can be bought, the output is 0
sample input
10 3
5 0
4 0
10 1
sample output
2 3
sample input
10 3
11 0
21 1
100 1
sample output
0
Data size and engagement
0 < s < = 10000, 0 < n < = 1000, each a and b meets 0 < a < = 1000 and b=0 or 1.
Train of thought: full brain thinks bubble sort, dizzy! Only by drawing lessons from the articles of the southern wall barons can we sort out the ideas clearly.
In fact, there are many conditions for judgment, which is troublesome
import java.nio.channels.Pipe; import java.util.Arrays; import java.util.Scanner; public class Main { static class Goods { // S / N discount int num, off; // Price double pic; // Initial values are all 0 public Goods() { num = 0; off = 0; pic = 0; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // Total price double S = scanner.nextInt(); // Number of items int N = scanner.nextInt(); // Array call, assign value to goods Goods[] arr = new Goods[N]; for (int i = 0; i < N; i++) { arr[i] = new Goods(); arr[i].pic = scanner.nextDouble(); arr[i].off = scanner.nextInt(); arr[i].num = i + 1; } // Buy first and earn the most for (int i = 0; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { if (arr[i].pic * arr[i].off < arr[j].pic * arr[j].off) { Goods temp; temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } // The most profitable buy the cheapest else if (arr[i].pic * arr[i].off == arr[j].pic * arr[j].off) { if (arr[i].pic > arr[j].pic) { Goods temp; temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } // If the order of purchase cannot be determined in the first two items, first buy the one in the top of the list else if (arr[i].pic == arr[j].pic) { if (arr[i].num > arr[j].num) { Goods temp; temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } } // Create a result array to store the serial number to be purchased int[] result = new int[N]; // Number of items stored int count = 0; // Purchase according to the order of number for (int i = 0; i < N; i++) { // Define a new variable to store the current price = original price - discount price double rpic = arr[i].pic - arr[i].pic * arr[i].off * 0.5; // Meeting conditions if (rpic <= S) { // Original price current price S -= rpic; // Result to original array result[count] = arr[i].num; // Statistics and count++; } } // If there is no product, output 0 and end the program if (count == 0) { System.out.print(0); System.exit(0); } // Sort item numbers Arrays.sort(result); // Export what you can buy for (int i = 0; i < N; i++) { if (result[i] != 0) { System.out.print(result[i] + " "); } } } }
