CF1168A Increasing by Modulo

思路：

首先得做个转化，如果某个解法最终分别对a[i](i = 1, 2, ..., n)做了b[i](i = 1, 2, ..., n)次加1再取余的运算，那么可以等价地构造出x次(x = max(b[i]))题目定义的操作，这样就可以直接对x二分了。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 300005;
 4 int a[N], n, m;
 5 bool check(int x)
 6 {
 7     int cur = 0;
 8     for (int i = 1; i <= n; i++)
 9     {
10         if (a[i] + x < cur) return false;
11         else if (a[i] > cur)
12         {
13             if (a[i] + x < m || (a[i] + x) % m < cur)
14                 cur = a[i];
15         }
16     }
17     return true;
18 }
19 int main()
20 {
21     while (cin >> n >> m)
22     {
23         for (int i = 1; i <= n; i++) cin >> a[i];
24         int l = 0, r = m, ans = m;
25         while (l <= r)
26         {
27             int mi = l + r >> 1;
28             if (check(mi))
29             {
30                 ans = mi;
31                 r = mi - 1;
32             }
33             else l = mi + 1;
34         }
35         cout << ans << endl;
36     }
37     return 0;
38 }