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;
}