CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. 杂项
  3. 正文

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

2022年9月2日 463点热度 0人点赞 0条评论

题意

题目链接: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;
}
标签: CodeForces 二分答案 贪心
最后更新:2022年9月3日

Carry

来自于湖南长沙

点赞
< 上一篇

文章评论

取消回复
标签
CodeForces 二分答案 贪心
文章目录
  • 题意
  • 思路
  • 代码
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

Codeforces Educational Round 122(Rated for Div.2)比赛总结 (rating+77)

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS