Problem Description
In their spare time, Holmes and Watson play a game:
N integers are written on N cards.Two people take a card in turn.The number required of the next person must be the approximate or multiple of the number taken by the previous person.For example, one time Holmes took a card with the number "6", Watson could then take the following numbers:
1，2，3, 6，12，18，24 ....
When it is a party's turn to take a card, if there is no card available that meets the requirements, the party is the loser.
Take advantage of your computer to figure out how you can choose to win given the numbers on all cards and the numbers you can choose from.
Output the smallest number when multiple numbers are selected to win.If you lose anyway, output-1.
Input Format
The input data is 2 rows.The first line is a space-separated integer (between 1 and 100 integers each) representing all the cards that are currently left.
The second line is also a space-separated integer representing the number that can be selected.Of course, the number in the second line must be completely contained in the number in the first line.
Output Format
The program outputs the winning tricks!!
sample input
2 3 6
3 6
sample output
3
sample input
1 2 2 3 3 4 5
3 4 5
sample output
4
Algorithmic ideas
The basic idea for this question is to let you pick the winning card out of the few available cards, and all we need to do is reduce the time complexity.
Because this is a combination of topics that grow exponentially, it is not easy to search.
My ways to reduce time complexity are:
- Once you've saved all the approximate multiples at first, you won't have to do that again
- Search from big to small, because when it's a few times larger, it's less than 100.Their approximation is almost no more than 10 very small.For example, 85 is about 5, 17.And when you start searching from 5, it multiplies by 5, 10, 15, 20, 25...
Specific code:
import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class SelectCard { static LinkedList<Integer> canselect;//Optional Cards static int[] cardnum = new int[101];//Number of digital cards static List[] cash = new List[101];//Store the approximate and multiple of each number public static void main(String[] args) { Scanner input = new Scanner(System.in); String inputall = input.nextLine(); String[] inputarr = inputall.split(" "); for (String i : inputarr) { cardnum[Integer.parseInt(i)]++; } canselect = new LinkedList<>(); inputall = input.nextLine(); inputarr = inputall.split(" "); for (String i : inputarr) canselect.add(Integer.parseInt(i)); // Save the next optional card after each card is pre-selected for (int i = 1; i <= 100; i++) { if (cardnum[i] == 0) continue; cash[i] = new ArrayList<Integer>(); for (int j = 1; j <= 100; j++) { if (j == i && cardnum[i] == 1) continue; if (cardnum[j] == 0) continue; if (j > i) { if (j % i == 0) cash[i].add(j); } else { if (i % j == 0) cash[i].add(j); } } } Collections.sort(canselect); Iterator<Integer> iter = canselect.iterator(); while (iter.hasNext()) { int tempno = iter.next(); cardnum[tempno]--; if (!f(tempno)) {//If the other side loses, we win the output System.out.println(tempno); return; } cardnum[tempno]++; } System.out.println(-1); } public static boolean f(int select) { //Optional cards, traversing from large to small for (int i = cash[select].size() - 1; i >= 0;i--) { int temp = (int) cash[select].get(i); if (cardnum[temp] > 0) { cardnum[temp]--; boolean flag = f(temp); cardnum[temp]++; if (!flag) return true; } } return false; } }