CF1168A - Increasing by Modulo (贪心+二分)

传送门:Problem - 1168A - Codeforces

定义操作使得ai变成(ai+1) mod m ,求对每个数进行的操作中最大操作数的最小值,使得序列不下降

因为m<=300000,枚举必炸,考虑对单个数操作数的最大值x进行二分

check函数:

思路:我们要使得序列前面的数尽量小,这样后面的数进行的操作数更少,更有可能出现单调不下降序列,x为此函数中单个数可以进行的操作的最大值。

我们在对一个数进行操作时,使用一个变量minn记录前一个数的值,我们在第i次操作时,有如下决策:

1.如果minn<=a[i]

(1)如果a[i]+x>=m,即操作后比m值大,可以通过取模的方式使得该数变小

那么令取模后的最大值为y=(a[i]+x)%m,如果y>=minn,说明a[i]进行至多x次的操作中取值范围涵盖了minn,这时可以直接令这个数为minn使得这个数最小即minn=minn

否则取模后的数的范围无法涵盖minn,这时这个数可以取的最小值只能是a[i]即minn=a[i]

(2)如果a[i]+x<m,易知此时的最小值minn只能为a[i]

2.如果minn>a[i]

不用考虑a[i]+x>=m,此时minn大于a[i],应先满足若干次操作后a[i]大于minn,进行操作使a[i]取模变小无意义

(1)如果a[i]+x>=minn,则此时最小值minn=minn

(2)如果a[i]+x<minn,说明此时进行了操作数达到最大后仍旧无法使得序列不下降,说明x值不符合条件,直接return 0

当循环完一遍后,序列构造完毕,最大操作数为x时可以满足条件,return 1

 

然后对x在0到m-1范围内进行二分查找即可

 

 

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int n,m;
int a[300010];
 
int check(int x)
{
    int minn=0;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        if(minn<=a[i])
        {
            if(a[i]+x>=m)
            {
            if((a[i]+x)%m>=minn)
            {
                continue;
            }
            else minn=a[i];
            }
            else minn=a[i];
        }
        
        else if(minn>a[i]&&minn<=a[i]+x)
        {
            continue;
        }
        
        else if(minn>(a[i]+x)){
            flag=1;
            break;
        }
    }
    return flag;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=0,r=m-1,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        int x=check(mid);
        if(x==1)
        {
            l=mid+1;
        }
        else if(x==0)
        {
            r=mid;
        }
    }
    cout<<r<<endl;
    return 0;
}

 

上一篇:2021-09-18


下一篇:leetcode 最小栈 简单