codeforces#562 Div2 C---Increasing by modulo【二分】

题目：http://codeforces.com/contest/1169/problem/C

题意：

有n个数，每次可以选择k个，将他们+1并对m取模。问最少进行多少次操作，使得序列是非递减的。

思路：

太久没刷题遭报应了。这两天能补多少是多少吧。

二分答案。然后看看这个序列是不是非递减的。

对于第i个数，如果$a[i]leq prevleq a[i]+mid$，说明在mid次操作内他肯定比他前一个数要大。

当然因为取模所以实际上还应该包括$a[i]leq prev+mleq a[i]+mid$

但如果$prev > a[i]+mid$说明mid不够大，则l = mid +1

否则r = mid

要死了二分都不会了。

 1 //#include<bits/stdc++>
 2 #include<stdio.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<stdlib.h>
 7 #include<queue> 
 8 #include<map>
 9 #include<stack>
10 #include<set>
11 
12 #define LL long long
13 #define ull unsigned long long
14 #define inf 0x7f7f7f7f 
15 
16 using namespace std;
17 
18 int n, m;
19 const int maxn = 3e5 + 5;
20 int num[maxn]; 
21 
22 int main()
23 {
24     scanf("%d%d", &n, &m);
25     for(int i = 0; i < n; i++){
26         scanf("%d", &num[i]);
27     }
28     int l = 0, r = m;
29     int ans;
30     while(l < r){
31         bool flag = false;
32         int mid = (l + r) / 2, prev = 0;
33         for(int i = 0; i < n; i++){
34             int x = num[i], y = num[i] + mid;
35             if(x <= prev && y >= prev || x <= prev + m && y >= prev + m){
36                 continue;
37             }
38             if(prev >= x){
39                 flag = true;
40                 break;    
41             }
42             prev = num[i];
43         }
44         if(flag){
45             l = mid + 1;
46         }
47         else{
48             //ans = mid;
49             r = mid;
50         }
51     }
52     printf("%d
", l);
53     return 0;    
54 }