CF 611 E. New Year Parties


输入 n(<=2e5) 和长为 n 的数组 a(1<=a[i]<=n)。
对于每个 a[i]，你可以将其 +1 或 -1，每个 a[i]至多修改一次。
输出修改后的 a 的不同元素个数的最小值和最大值。
不同元素个数即 len(set(a))。

思路：
最大值 ： 排序 + 贪心
能减就减，不能减的话，能保持尽量保持，不能保持，就加一
最小值：计数 + 贪心
考虑上一个使用的位置，能和就和，不能和就加一（向上靠拢）

  1. static final int N = 200010;
  2. static int[] a = new int[N], b = new int[N];
  3. static int n;
  4. static void solve() {
  5.     n = ni();
  6.     for (int i = 0; i < n; i++) {
  7.         a[i] = ni();
  8.         b[a[i]]++;
  9.     }
  10.     Arrays.sort(a, 0, n);
  12.     int max = 0;
  13.     Set<Integer> set = new HashSet<>();
  14.     for (int i = 0; i < n; i++) {
  15.         if (!set.contains(a[i] - 1))
  16.             set.add(a[i] - 1);
  17.         else if (!set.contains(a[i]))
  18.             set.add(a[i]);
  19.         else
  20.             set.add(a[i] + 1);
  21.     }
  22.     max = set.size();
  24.     int min = 0, pre = -1;
  26.     for (int i = 1; i <= n; i++) {
  27.         if (b[i] == 0) continue;
  28.         if (pre == i - 1 || pre == i) {
  29.             continue;
  30.         } else {
  31.             min++;
  32.             pre = i + 1;
  33.         }
  34.     }
  36.     out.println(min + " " + max);
  39. }

CF 802 F. Puzzle

给定2行n列的01原数组，以及2行n列的目标数组，问将原数组通过交换相邻位置元素，最少需要多少步能变至目标数组，若无合法方案，输出-1

输入：
第一行表示n
第2，3行为各有n 个用空格分隔的数字，表示原数组
第4，5行为各有n 个用空格分隔的数字，表示目标数组

输出
最小步数，若没有，输出-1

思路：
将原数组中的1按是否在目标集合中分为两类，第一种是变换前已经在目标位置中，第二种是在变换前不在目标位置中。
先考虑1维的情况
如果某个1已经在目标集和中，说明不用对其进行操作，代价为0
如果某个1不在目标集和中，说明需要将其移动至目标集和中，代价移动步数
具体做法：将在集和中的已经有数字的位置记为0，没有数字的记为-1，将在集和外的数字对应位置记为1
从前往后，计算前缀和，若当前前缀和x大于0，说明有x个数还未移动至目标集中，每个都还需1步，总代价res += x
若当前前缀和x小于0，说明有x个目标集中的位置缺数，总代价为res += -x

考虑二维情况
如果某一位置，两维前缀和异号，说明可将上面一个数字移动至下边的目标集，或者将下面的一个数字移动至上面的目标集中，总代价 +1.

  1. static final int N = 200010;
  2. static int[][] a = new int[2][N];
  3. static int[][] b = new int[2][N];
  4. static int n;
  5. static void solve() {
  6.     n = ni();
  8.     int s1 = 0, s2 = 0;
  9.     for (int i = 0; i < 2; i++) {
  10.         for (int j = 1; j <= n; j++) {
  11.             a[i][j] = ni();
  12.             s1 += a[i][j];
  13.         }
  14.     }
  17.     for (int i = 0; i < 2; i++) {
  18.         for (int j = 1; j <= n; j++) {
  19.             b[i][j] = ni();
  20.             s2 += b[i][j];
  21.         }
  22.     }
  23.     if (s1 != s2) {
  24.         out.println(-1);
  25.         return;
  26.     }
  28.     for (int i = 1; i <= n; i++) {
  29.         if (b[0][i] == 1) {
  30.             if (a[0][i] == 1)
  31.                 a[0][i] = 0;
  32.             else a[0][i] = -1;
  33.         }
  34.         if (b[1][i] == 1) {
  35.             if (a[1][i] == 1)
  36.                 a[1][i] = 0;
  37.             else a[1][i] = -1;
  38.         }
  39.     }
  42.     long p1 = 0, p2 = 0;
  43.     long res = 0;
  44.     for (int i = 1; i <= n; i++) {
  45.         p1 += a[0][i];
  46.         p2 += a[1][i];
  47.         if (p1 * p2 >= 0)
  48.             res += Math.abs(p1) + Math.abs(p2);
  49.         else {
  50.             long x = Math.min(Math.abs(p1), Math.abs(p2));
  51.             if (p1 < 0) p1 += x;
  52.             else p1 -= x;
  53.             if (p2 < 0) p2 += x;
  54.             else p2 -= x;
  55.             res++;
  56.             res += Math.abs(p1) + Math.abs(p2);
  57.         }
  58.     }
  59.     out.println(res);
  60. }

CF 605A. Sorting Railway Cars

题意描述：
给定一个长度为n的数组，不超过100000。
数组中的所有数正好是1-n的某个排列。
每次操作如下：任选一个数放在队头或队尾
问最少几次操作使数组按递增顺序排列？
输入：
第一行，一个整数n表示数组长度
第二行，空格隔开的n个整数(ai != aj && 1 <= ai,aj <= n)
思路：
一次移动一定能将一个数字放到其应在的位置
排好序后的序列和原序列相比，考虑有哪些数没有移动过！
没有动过的数中间一定不会再有别的数字
即找数值连续的最长上升子序列或排序后的下标最长递增子数组(连续)

  1. // 数值连续的最长上升子序列
  2. static int N = 100010;
  3. static int[] a = new int[N];
  4. static int[] f = new int[N];
  5. static int n;
  6. static void solve() {
  7.     n = ni();
  8.     for (int i = 1; i <= n; i++) a[i] = ni();
  10.     int max = 0;
  11.     for (int i = 1; i <= n; i++) {
  12.         f[a[i]] = f[a[i] - 1] + 1;
  13.         max = Math.max(max, f[a[i]]);
  14.     }
  15.     out.println(n - max);
  16. }
  1. // 下标最长递增子数组
  2. static int N = 100010;
  3. static int[][] a = new int[N][2];
  4. static int[] b = new int[N];
  5. static int[] f = new int[N];
  6. static int n;
  7. static void solve() {
  8.     n = ni();
  9.     for (int i = 1; i <= n; i++) {
  10.         a[i][0] = ni();
  11.         a[i][1] = i;
  12.     }
  13.     Arrays.sort(a, 1, n + 1, (o1, o2) -> (o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]));
  15.     int max = 0;
  16.     int c = 0;
  17.     for (int i = 1; i <= n; i++) {
  18.         if (a[i][1] > a[i - 1][1]) {
  19.             c++;
  20.         } else {
  21.             c = 1;
  22.         }
  23.         max = Math.max(max, c);
  24.     }
  25.     out.println(n - max);
  26. }

扩展：
如果原数组取值任意怎么办？