LightOJ[1303]

Problem 
1303 - Ferris Wheel

Idea Flow

Input_Constraint ~ Total number of passengers and total number of seats are 20, 20 respectively.

Question Hints ~ Cake Walk

Conclusion ~ proper use of indexing and arrayList can solve the problem.

Learnt lesson ~ Solver need to analyze the time complexity.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

package net.egork; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.io.PrintWriter; public class L1303 { private static final String CASE = "Case"; private static final String SPACE = " "; private static final String COLON = ":"; int n, m, cursor; private int totalTime; public void solve(int testNumber, Scanner in, PrintWriter out) { int testCase; testCase = in.nextInt(); for (int i = 1; i <= testCase; i++) { cursor = 0; totalTime = 0; n = in.nextInt(); m = in.nextInt(); int dp[][] = new int[n + 2][m + 2]; int circularArray[] = new int[m + 2]; List<Integer> integerList = new ArrayList<Integer>(); for (int j = 1; j <= n; j++) integerList.add(j); do { cursor = (cursor + 1) % m; int outPerson = circularArray[cursor]; circularArray[cursor] = 0; if (isNeeded(dp, outPerson)) { integerList.add(outPerson); } int findPerson = getPerson(integerList, dp); if (findPerson >= 0) { int personNumber = integerList.get(findPerson); dp[personNumber][cursor] = 1; integerList.remove(findPerson); circularArray[cursor] = personNumber; } totalTime += 5; } while (!isFWEMPTY(circularArray)); System.out.println(CASE + SPACE +i + COLON + SPACE + totalTime); } } private boolean isFWEMPTY(int[] circularArray) { for (int i = 0; i < m; i++) { if (circularArray[i] > 0) return false; } return true; } private boolean isNeeded(int[][] dp, int person) { if (person == 0) return false; for (int i = 0; i < m; i++) { if (dp[person][i] == 0) return true; } return false; } private int getPerson(List<Integer> integerList, int[][] dp) { int sz = integerList.size(); for (int i = 0; i < sz; i++) { if (dp[integerList.get(i)][cursor] == 0) { return i; } } return -1; } }