UVA-12174 Shuffle的播放记录 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版使用滑动窗口方法来做但是要注意滑动一个元素之后这个窗口便属于另外一种可能性。滑动到下一个元素时将窗口外的前一个元素删除新的元素增加进来。如果某个元素的数量大于2说明这个这个窗口不符合条件对应的可能性删除。下面的方法中wnum是排列的个数。例如10个历史记录歌曲数为4时可能有3-5个排列每个排列往前加s为下一个排列。step为每个窗口的起始点也就是step在滑动。滑动前还要计算初始的元素的排列是否符合要求。我这个实现有点繁琐应该有更简单的方式。AC代码#include stdio.h #include string.h #define MAXN 100005 int arrn[MAXN]; int s, n; int arrs[MAXN]; int steps[MAXN]; void computed() { int wnum, step; int i, j, k; int num2 0; memset(steps, 0, sizeof(steps)); for (wnum 0;; wnum) { memset(arrs, 0, sizeof(arrs)); // 计算初始值 num2 0; for (i (wnum - 1) * s - 1; i wnum * s - 1; i) { if (i 0 || i n) continue; arrs[arrn[i]] 1; if (arrs[arrn[i]] 2) num2; } for (step 0; step s; step) { i step (wnum - 1) * s; if (i - 1 n) return; // 减去前一个增加下一个 if (i - 1 0) { if (arrs[arrn[i - 1]] 2) --num2; arrs[arrn[i - 1]]--; } if (i s - 1 n) { arrs[arrn[i s - 1]]; if (arrs[arrn[i s - 1]] 2) num2; } if (num2 0) steps[step] 1; } } } int main() { int t, i, j; scanf(%d, t); while (t--) { scanf(%d %d, s, n); for (i 0; i n; i) scanf(%d, arrn[i]); computed(); j 0; for (i 0; i s; i) { if (steps[i] 0) j; } printf(%d\n, j); } return 0; }