【HDU】5248-序列变换(贪心+二分)「建议收藏」

【HDU】5248-序列变换(贪心+二分)

大家好,又见面了,我是全栈君。

二分枚举长度改变的长度即可了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int  INF = 3000000;
const int maxn = 100005;
int n,arr[maxn],arr2[maxn];
bool solve(int x){
    memcpy(arr2,arr,sizeof(arr));
    for(int i = 1; i <= n; i++){
        if(arr2[i] > arr2[i - 1]){
            arr2[i] = max(arr2[i - 1] + 1,arr2[i] - x);
        }
        else{
            if(arr2[i] + x <= arr2[i - 1]) return false;
            arr2[i] = arr2[i - 1] + 1;
        }
    }
    return true;
}
int main(){
    int T,Case = 1;
    scanf("%d",&T);
    arr[0] = -INF;
    while(T--){
        scanf("%d",&n);
        for(int i = 1; i <= n; i++)
            scanf("%d",&arr[i]);
        int l = 0,r = INF;
        int ans = n;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(solve(mid)){
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        printf("Case #%d:\n",Case++);
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116609.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 光场相机介绍_光场相机是什么

    光场相机介绍_光场相机是什么魅族在flyme3.3上推出光场相机:

  • pl/sql developer使用教程13_PLSQL Developer

    pl/sql developer使用教程13_PLSQL Developer.Net程序员学用Oracle系列(18):PLSQLDeveloper攻略1、功能说明及使用技巧1.1、对象浏览器1.2、SQL窗口1.3、测试窗口1.4、命令窗口1.5、图表窗口

  • 小程序点击复制功能_怎么复制小程序链接

    小程序点击复制功能_怎么复制小程序链接先来说明一下我们需要实现的最终效果:用户点击之后复制页面内容。参考详情一、长按复制:长按复制,在微信小程序内的文字无法长按复制,除了text节点以外,但是要在text标签内加一个“selectable”属性。话不多说,我们直接上代码1.WXML<textselectable=”true”>长按复制<text/>二、一键复制:添加点击事件,绑定…

  • phpstorm2021 激活码【2021免费激活】

    (phpstorm2021 激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~2QQ4OQYW6M-eyJsaWNlb…

  • postman调试rpc接口

    postman调试rpc接口使用postman测试RPC接口PostMan如何调用RPC接口(postman下载)PostMan如何调用RPC接口接口调试之Postman使用方法详解

    2022年10月13日
  • HBase面试题精讲「建议收藏」

    HBase面试题精讲「建议收藏」1.HBase的特点是什么?1)大:一个表可以有数十亿行,上百万列;2)无模式:每行都有一个可排序的主键和任意多的列,列可以根据需要动态的增加,同一张表中不同的行可以有截然不同的列;3)面向列:面向列(族)的存储和权限控制,列(族)独立检索;4)稀疏:空(null)列并不占用存储空间,表可以设计的非常稀疏;5)数据多版本:每个单元中的数据可以有多个版本,默认情况下版本号自动分配,是单元格插入时的时间戳;6)数据类型单一:Hbase中的数据都是字符串,没有类型。2.HBase和Hive

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号