Codeforces 1168A Increasing by Modulo

题目链接：http://codeforces.com/problemset/problem/1168/A

题意：给一个数组，数组中元素范围为0~n，每次你可以选择若干元素进行(ai+1)%m的操作，问使数组呈非递增的最小操作次数。

思路：因为每次都可以选若干个元素，用贪心思想，假设要操作x次，第一个元素加上x若能超过m，则对m取模最小值为0，令其等于0就好了，后面每个元素加上x后，对m取模后只要不比前面小就好了，则依次判断数组的每个元素能否满足，利用二分搜索来寻找操作数 x，x即为答案。

AC代码：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn = 3e5 + ;

 int a[maxn];

 int n,m;

 bool check(int x)

 {

     int last = a[];

     if(a[] + x >= m) last = ;//如果 a[0] 经过x次变换后大于 m 那么 a[0] 可以看做 0 。

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

     {

         int temp = -;//存放a[i]与last更大的那个。

         if(a[i] >= last)

         {

             temp = a[i];

             //如果经过x次变换后 a[i] 可以比前面大，那么temp存放前面的值就行。

             if(a[i] + x >= m && (a[i] + x) % m >= last)

             {

                 temp = last;

             }

         }

         else if(a[i] + x >= last) temp = last;

         if(temp == -) return false;//找不到比前面更大的a[i]。

         last = temp;

     }

     return true;

 }

 int main()

 {

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

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

     {

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

     }

     int l = ,r = m + ,ans = ;

     while(l <= r)

     {

         int mid = (l + r) >> ;

         if(check(mid)) r = mid - ,ans = mid;

         else l = mid + ;

     }

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

     return ;

 }

巴特西

Codeforces 1168A Increasing by Modulo

最新文章

热门文章