题意
题目链接: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;
}
文章评论