CF 847 E. Packmen

给你一个整数 n(<=1e5) 和一个长为 n 的字符串 s（包含 P. 三种字符，其中 ‘P’ 表示动物，’‘ 表示食物，’.’ 表示空地）。
所有动物每单位时间均能移动一个单位，动物移动到食物上就会吃掉食物，吃掉食物的时间忽略不计。
所有动物可以一起移动。请问吃掉所有食物最少需要多少时间。

思路：
一道较难的二分题
二分+ 双指针
check函数：考虑每个动物向左还是向右(使利益最大化，(吃完前面食物的情况下)向右的步数最多)

  1. static final int N = 100010;
  2. static int n;
  3. static void solve() {
  4.     n = ni();
  5.     char[] ch = ns().toCharArray();
  7.     int l = 1, r = 2 * n;
  8.     while (l < r) {
  9.         int mid = l + r >> 1;
  10.         boolean flag = true;
  11.         for (int i = 0, j = 0, pos = -1; i < n; i++) {
  12.             if (ch[i] != '*' || pos >= i)
  13.                 continue;
  14.             while (j < n && ch[j] != 'P')
  15.                 j++;
  16.             if (j >= n) {
  17.                 flag = false;
  18.                 break;
  19.             }
  21.             if (j < i) {
  22.                 pos = j + mid;
  23.                 j++;
  24.                 i--;
  25.             } else {
  26.                 if (j - i > mid) {
  27.                     flag = false;
  28.                     break;
  29.                 }
  30.                 pos = Math.max(i + mid - (j - i), j + (mid - (j - i)) / 2);
  31.                 j++;
  32.             }
  34.         }
  36.         if (flag)
  37.             r = mid;
  38.         else
  39.             l = mid + 1;
  40.     }
  41.     out.println(l);
  42. }

CF 1168 A. Increasing by Modulo

输入 n (1≤n≤3e5)、m (1≤m≤3e5) 和一个长为 n 的数组 a，元素值在 [0,m-1] 内。每次操作，你可以选择 a 中的某些数，把每个数 x 改成 (x+1)%m。输出使 a 变成单调非降的最少操作次数。

思路：贪心 + 二分
考虑二分操作数αα，因为每次可以选取任意个数进行操作，所以每个数的操作次数都是 0∼α0∼α 且相互独立。
我们可以记录上一个数的值 LastLast ，显然LastLast越小答案不会更劣，对当前的AiAi而言：

  • 如果Ai⩽Last⩽Ai+α，我们可以直接将Ai加到Last即可
  • 如果Ai>Last 且 (Ai+α)%m⩾Last，我们也可以将Ai加到Last
  • 如果Ai>Last 且 (Ai+α)%m<Last，那我们就不对Ai操作
  • 如果Ai<Last 且 Ai+α<Last，那无论怎么操作都不可行
  1. static final int N = 300010;
  2. static int[] a = new int[N];
  3. static int n, m;
  4. static void solve() {
  5.     n = ni();
  6.     m = ni();
  7.     for (int i = 1; i <= n; i++)
  8.         a[i] = ni();
  9.     int l = 0, r = m;
  10.     while (l < r) {
  11.         int mid = l + r >> 1;
  12.         boolean flag = true;
  13.         int pre = 0;
  14.         for (int i = 1; i <= n; i++) {
  15.             if (a[i] >= pre) {
  16.                 if (a[i] + mid >= m) {
  17.                     if ((a[i] + mid) % m < pre) pre = a[i];
  18.                 } else pre = a[i];
  19.             } else if (a[i] + mid < pre) {
  20.                 flag = false;
  21.                 break;
  22.             }
  23.         }
  24.         if (flag) r = mid;
  25.         else l = mid + 1;
  26.     }
  27.     out.println(l);
  28. }