# Blue bridge algorithm bubble sorting double eleven rush

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.

## 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] + " ");
}
}
}
}
```

## Small theater: put down the keyboard to be killed  45 original articles published, 25 praised, 5973 visited

Keywords: Java

Added by CountryGirl on Fri, 21 Feb 2020 11:56:42 +0200