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

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

题意：

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

思路：

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

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

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

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

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

否则r = mid

要死了二分都不会了。

 //#include<bits/stdc++>

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<stdlib.h>

 #include<queue>

 #include<map>

 #include<stack>

 #include<set>

 #define LL long long

 #define ull unsigned long long

 #define inf 0x7f7f7f7f 

 using namespace std;

 int n, m;

 const int maxn = 3e5 + ;

 int num[maxn]; 

 int main()

 {

     scanf("%d%d", &n, &m);

     for(int i = ; i < n; i++){

         scanf("%d", &num[i]);

     }

     int l = , r = m;

     int ans;

     while(l < r){

         bool flag = false;

         int mid = (l + r) / , prev = ;

         for(int i = ; i < n; i++){

             int x = num[i], y = num[i] + mid;

             if(x <= prev && y >= prev || x <= prev + m && y >= prev + m){

                 continue;

             }

             if(prev >= x){

                 flag = true;

                 break;

             }

             prev = num[i];

         }

         if(flag){

             l = mid + ;

         }

         else{

             //ans = mid;

             r = mid;

         }

     }

     printf("%d\n", l);

     return ;

 }

巴特西

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

最新文章

热门文章