CF1168A – A Increasing by Modulo 二分答案+贪心 1700

题意

题目链接：https://codeforces.com/contest/1168/problem/A
题意：给出 $n,m$，以及 $m$ 个数 $a_1,a_2,\cdots ,a_m$，你可以执行以下操作：

• 选择若干个$a_i$使其变成$(a_i+1) \% n$

问使得$a$数组不下降的最小次数

思路

首先来看这个若干的意思，每次可以选择一些说明不是只让一个，那么例如我$a[2]$需要操作$3$次，$a[5]$需要操作$2$次，最小次数不是$5$次而是$3$次，可以看出这里是这些操作的最大值。

那么如何做呢？观察到假如答案是ans，那么从$1～ans-1$都是不可以的，而$ans$以后是可以的，所以可以进行二分答案。

每次二分的是次数$x$，说明这$m$个数可以最多进行操作$x$次，我们用贪心的思想来看，设pre是上一个数的值，则有：

• 如果 $a[i]\lt pre$。说明我们至少要要把当前的$a[i]$提升到上一个相等的$pre$，判断我此时的$x$是否可以达成，否则返回false
• 如果 $a[i]\gt pre$。说明我需要跨过$n-1$让当前的$a[i]$变成$0$，然后再变成$pre$最好，这个时候的次数是$pre+m-a[i]$，与$x$比较，如果不可以，那么就是返回false

主要要注意到的是，我当前的数字最好要贴紧上一个数字最好，这样就是贪心的思想

    auto check = [&](int x)
    {
        int pre = 0;
        for (int i=1;i<=n;i++)
        {
            if (a[i]<=pre)
            {
                if (pre-a[i]>x) return false;
            }
            else//a[i]>pre
            {
                if (pre+m-a[i]>x) pre = a[i];  
            }
        }
        return true;
    };

代码

inline void Case_Test()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    int l = 0, r = m;
    auto check = [&](int x)
    {
        int pre = 0;
        for (int i=1;i<=n;i++)
        {
            if (a[i]<=pre)
            {
                if (pre-a[i]>x) return false;
            }
            else//a[i]>pre
            {
                if (pre+m-a[i]>x) pre = a[i];  
            }
        }
        return true;
    };
    while (l<r)
    {
        int mid = (l+r)>>1;
        if (check(mid)) r = mid;
        else l = mid+1;
    }
    cout<<l;
}