好不容易来到新的一关，有一个长长的吊桥，吊桥的尽头是下水管道，其中随机的木板存在缺失，一旦踩到就会死亡，死亡后如果还有剩余的生命将在原地复活且不受木板缺失影响，但会消耗一次生命；如果跨过了管道，将跌入悬崖，通关失败。超级玛丽从起点S开始，可以走到下个木板(计+1)，也可以跳着跨过一个块(计2)或两个木板(计3)，最终必须刚好走到终点
现在给定超级玛丽当前的生命数M,吊桥的长度N,缺失的木板数K,以及随机缺失的木板编号数组L，请帮忙计算一下，超级玛丽有多少种方法可以通过此关
解答要求
时间限制：C/C++ 1000ms，其他语言: 2000ms 内存限制：C/C++ 256MB，其他语言：512MB
输入
超级玛丽当前生命数: M (1<=M<=5, 整数) 吊桥的长度: N (1 <=N<=32,整数) 缺失木板数: K (1<=N<=32,整数) 缺失木板编号数组: L (长度及编号的内容不大于N的编号数组， 1<=Li<=N
输出
输出通过此关的吊桥走法个数，如果不能通过此关，请输出0
样例1
输入:2 2 1 4 输出:4 解释: 2个生命，2个木板，缺失1个木板 第2个木板有缺失，一共有 4种走法:
样例2
输入:1 3 2 1 3 输出:1 解释: 1个生命，3个木板，缺失2个木板 第1个和第3个有缺失 只有一种走法: 2, 2,其他都不能通关:
x
public class Bridge { private int[] L; private int M, N, K; private int[][] emeo; private Set<Integer> set; // 记忆化搜索「回溯」 public int f1(int M, int N, int K, int[] L) { this.M = M; this.N = N; this.K = K; this.L = L; emeo = new int[N + 2][M + 1]; set = new HashSet<>(); for (int i : L) set.add(i); for (int i = 0; i <= N + 1; i++) Arrays.fill(emeo[i], -1); return backtrack(0, M); } private int backtrack(int i, int j) { if (i > N + 1 || j == 0) return 0; if (i == N + 1) return 1; if (emeo[i][j] != -1) return emeo[i][j]; int life = set.contains(i) ? j - 1 : j; emeo[i][j] = backtrack(i + 1, life) + backtrack(i + 2, life) + backtrack(i + 3, life); return emeo[i][j]; } // dp public int f2(int M, int N, int K, int[] L) { Set<Integer> set = new HashSet<>(); for (int i : L) set.add(i); // dp[i][j] 表示「在位置 i，还剩 j 条命」的通关走法个数 int[][] dp = new int[N + 2][M + 1]; // base case：在位置 0，通关走法个数为 1 // dp[0][0 ... M - 1] = 0，因为 这些情况都是不存在的！！ dp[0][M] = 1; for (int i = 1; i <= N + 1; i++) { for (int j = 1; j <= M - (set.contains(i) ? 1 : 0); j++) { int life = set.contains(i) ? j + 1 : j; for (int k = 1; k <= 3 && i - k >= 0; k++) { dp[i][j] += dp[i - k][life]; } } } int ans = 0; for (int i = 1; i <= M; i++) ans += dp[N + 1][i]; return ans; } // dp「AC 代码」 public int f3(int M, int N, int K, int[] L) { Set<Integer> set = new HashSet<>(); for (int i : L) set.add(i); int[][] dp = new int[N + 2][M + 1]; dp[0][M] = 1; for (int i = 1; i <= N + 1; i++) { boolean trap = set.contains(i); int t = trap ? 1 : 0; for (int j = 1; j <= M - t; j++) { if (i >= 1) { if (trap) dp[i][j] += dp[i - 1][j + 1]; else dp[i][j] += dp[i - 1][j]; } if (i >= 2) { if (trap) dp[i][j] += dp[i - 2][j + 1]; else dp[i][j] += dp[i - 2][j]; } if (i >= 3) { if (trap) dp[i][j] += dp[i - 3][j + 1]; else dp[i][j] += dp[i - 3][j]; } } } return Arrays.stream(dp[N + 1]).sum(); }
public static void main(String[] args) { Bridge bridge = new Bridge(); Random random = new Random(); // 造数据 for (int i = 0; i < 100; i++) { int M = random.nextInt(5) + 1, N = random.nextInt(32) + 1, K = random.nextInt(N) + 1; int[] broken = new int [K]; Set<Integer> set = new HashSet<>(); int cnt = 0; while (cnt < K) { int cur = random.nextInt(N) + 1; if (set.contains(cur)) continue; set.add(cur); broken[cnt++] = cur; } // System.out.println(M + "--" + N + "--" + K); // System.out.println(Arrays.toString(broken)); int r1 = bridge.f1(M, N, K, broken); int r2 = bridge.f2(M, N, K, broken); int r3 = bridge.f3(M, N, K, broken); System.out.println((r1 == r2 && r1 == r3) + "--" + r1 + "--" + r2 + "--" + r3); } }
}有一批数据包需要传输，每个数据包大小不一样,传输需要不同的时长，现在有N个传输通道，每个通道的大小也不一样,通道只能传输小于等于自己大小的数据包，不同通道可以同时传输数据包，通道中可以缓存多个数据包，当新任务来时，可以先进入缓存队列等待发送，问最短需要多长时间能够传输完成，通道会确保所有数据包都可以传输
解答要求
时间限制: C/C++ 1500ms,其他语言: 3000ms 内存限制: C/C++ 256MB，其他语言: 512MB
输入
第一行MN, M表示队列长度，N表示传输通道数第二行有N个数，表示每个通道的大小P 第三行有M个数，表示每个数据包的大小Q第四行有M个数，表示每个数据包传输时长S 1 <=M,S, P, Q <= 10000 1 <=N <= 1000
输出
输出传输完所有数据包需要的最短时长
样例1
输入: 5 2 5 3 1 4 5 2 3 1 6 10 3 4 输出:16 解释:数据包3进入通道1，数据包2进入通道1，输数据包5进入通道2，数据句4进入通道2，数据包1讲入通道2:通道1的传输时长是10+6=16，通道2的传输时长是3+2+1=8，这样最短时长就为16
样例2
输入:3 2 6 13 2 11 5 3 25 14 输出:25 解释:数据包2进入通道2数据包3进入通道1数据包1进入通道1:通道1的传输时长是14+3=17，通道2的传输时长是25，这样最短时长就为25
贪心策略一：按照数据包大小递减排序，处于同一区间的数据包按照时间递减排序
贪心策略二：按照数据包传输时间递减排序，时间相同，按照数据包大小递减排序，如果有多个通道结束时间相同，选择更小的通道
坑：大小和时间成正比
xxxxxxxxxxpublic class Transition {
// 贪心策略一 public int f1(int M, int N, int[] P, int[] Q, int[] S) { Integer[] idx = IntStream.range(0, M).boxed().toArray(Integer[]::new); Arrays.sort(idx, (a, b) -> Integer. compare(Q[b], Q[a])); Arrays.sort(P);
List<Integer> list = new ArrayList<>(); List<Integer>[] lists = new ArrayList[N]; for (int i = 0; i < N; i++) lists[i] = new ArrayList<>(); for (int i = N - 1, j = 0; i >= 0; i--) { // 通道的上下界 int lo = i == 0 ? 0 : P[i - 1], hi = P[i]; // 按照通道分组 while (j < idx.length && lo < Q[idx[j]] && Q[idx[j]] <= hi) lists[N - i - 1].add(idx[j++]); // 组内排序 lists[N - i - 1].sort((a, b) -> S[b] - S[a]); // 合并分组 list.addAll(lists[N - i - 1]); } // for (int i = 0; i < list.size(); i++) { // System.out.println(Q[list.get(i)] + "--" + S[list.get(i)]); // } Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); int cnt = N - 1; for (int i = 0; i < M; i++) { if (cnt >= 0 && Q[list.get(i)] <= P[cnt]) { pq.offer(new int[]{P[cnt--], 0}); } int[] cur = pq.poll(); cur[1] += S[list.get(i)]; pq.offer(cur); } int ans = 0; while (!pq.isEmpty()) { int[] cur = pq.poll(); ans = Math.max(ans, cur[1]); } return ans; } // 贪心策略二 public int f2(int M, int N, int[] P, int[] Q, int[] S) { Integer[] idx = IntStream.range(0, M).boxed().toArray(Integer[]::new); Arrays.sort(idx, (a, b) -> { // 先根据时间排序 if (S[a] != S[b]) return S[b] - S[a]; return Q[b] - Q[a]; // 再根据大小排序 }); Arrays.sort(P); int[] time = new int[N]; for (int i = 0; i < M; i++) { int curQ = Q[idx[i]], curS = S[idx[i]]; // 挑选出最优通道：能处理该数据包的最小通道 Queue<Integer> pq = new PriorityQueue<>((a, b) -> { if (time[a] != time[b]) return time[a] - time[b]; else return P[a] - P[b]; }); // 将所有可能处理该数据包的通道加入队列 for (int j = N - 1; j >= 0 && curQ <= P[j]; j--) pq.offer(j); time[pq.poll()] += curS; } int ans = 0; for (int i = 0; i < N; i++) ans = Math.max(ans, time[i]); return ans; } // 贪心策略二「AC 代码」 public int f3(int M, int N, int[] P, int[] Q, int[] S) { Arrays.sort(P); int[] times = new int[N]; Queue<Integer> idx = new PriorityQueue<>((a, b) -> { // 先根据时间排序 // if (S[a] != S[b]) return S[b] - S[a]; // return Q[b] - Q[a]; // 再根据大小排序 if (Q[a] != Q[b]) return Q[b] - Q[a]; else return S[b] - S[a]; }); for (int i = 0; i < M; i++) idx.offer(i); while (!idx.isEmpty()) { int i = idx.poll(); int large = Q[i]; int cost = S[i];
int min = Integer.MAX_VALUE; int min_p = -1; Queue<Integer> ch = new PriorityQueue<>((a, b) -> { if (times[a] == times[b]) return P[a] - P[b]; else return times[a] - times[b]; }); for (int j = N - 1; j >= 0 && P[j] >= large; j--) ch.offer(j); times[ch.poll()] += cost; } int ans = 0; for (int i = 0; i < N; i++) ans = Math.max(ans, times[i]); return ans; } public int f4(int M, int N, int[] P, int[] Q, int[] S) { Integer[] idx = new Integer[M]; for (int i = 0; i < M; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> { if (Q[a] != Q[b]) return Q[b] - Q[a]; else return S[b] - S[a]; }); // Queue<int[]> pq = new PriorityQueue<>((a, b) -> { // if (a[1] != b[1]) return a[1] - b[1]; // else return a[0] - b[0]; // }); Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); Arrays.sort(P); int cnt = N - 1; for (int i = 0; i < M; i++) { if (cnt >= 0 && Q[idx[i]] <= P[cnt]) { pq.offer(new int[]{P[cnt--], 0}); } int[] cur = pq.poll(); cur[1] += S[idx[i]]; pq.offer(cur); } int ans = 0; while (!pq.isEmpty()) { int[] cur = pq.poll(); ans = Math.max(ans, cur[1]); } return ans; } public int f5(int M, int N, int[] P, int[] Q, int[] S) { Integer[] idx = IntStream.range(0, M).boxed().toArray(Integer[]::new); Arrays.sort(idx, (a, b) -> { if (Q[a] != Q[b]) return Q[b] - Q[a]; else return S[b] - S[a]; }); Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); Arrays.sort(P); int cnt = N - 1; pq.offer(new int[]{P[cnt--], 0}); for (int i = 0; i < M; i++) { if (cnt >= 0 && Q[idx[i]] <= P[cnt]) { pq.offer(new int[]{P[cnt--], 0}); } int[] cur = pq.poll(); cur[1] += S[idx[i]]; pq.offer(cur); } int ans = 0; while (!pq.isEmpty()) { int[] cur = pq.poll(); ans = Math.max(ans, cur[1]); } return ans; } public static void main(String[] args) { Transition transition = new Transition(); int sz = 100000; Random random = new Random(); for (int i = 0; i < 10000; i++) { int M = random.nextInt(sz) + 1, N = random.nextInt(1000) + 1; int[] P = new int[N]; int cnt = 0, max = 0; Set<Integer> set = new HashSet<>(); while (cnt < N) { int cur = random.nextInt(sz) + 1; if (set.contains(cur)) continue; set.add(cur); P[cnt++] = cur; max = Math.max(max, cur); } int[] Q = new int[M], S = new int[M]; cnt = 0; while (cnt < M) { Q[cnt] = random.nextInt(max) + 1; S[cnt] = (int) (Q[cnt] * 0.9) + 10; // S[cnt] = random.nextInt(max) + 1; cnt++; } int r1 = transition.f1(M, N, Arrays.copyOf(P, N), Arrays.copyOf(Q, M), Arrays.copyOf(S, M)); int r2 = transition.f2(M, N, Arrays.copyOf(P, N), Arrays.copyOf(Q, M), Arrays.copyOf(S, M)); int r3 = transition.f3(M, N, Arrays.copyOf(P, N), Arrays.copyOf(Q, M), Arrays.copyOf(S, M)); int r4 = transition.f4(M, N, Arrays.copyOf(P, N), Arrays.copyOf(Q, M), Arrays.copyOf(S, M)); int r5 = transition.f5(M, N, Arrays.copyOf(P, N), Arrays.copyOf(Q, M), Arrays.copyOf(S, M)); System.out.println((r1 == r2 && r1 == r3 && r1 == r4 && r1 == r5) + "--" + r1 + "--" + r2 + "--" + r3 + "--" + r4 + "--" + r5); } }}