【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)


相关推荐

  • volatile关键字到底有什么作用

    volatile关键字到底有什么作用提示:更多优秀博文请移步博主的GitHub仓库:GitHub学习笔记、Gitee学习笔记volatile是Java提供的一种轻量级的同步机制。Java语言包含两种内在的同步机制:同步块(或方法)和volatile变量,相比于synchronized(synchronized通常称为重量级锁),volatile更轻量级,因为它不会引起线程上下文的切换和调度。但是volatile变量的同…

  • 在线H5页面生成器(持续更新中)

    在线H5页面生成器(持续更新中)1、关键词搜索wysiwyg,staticsitegenerator,h5creator,h5edtitor,h5maker2、原理讲解(重点)https://github.com/CntChen/cntchen.github.io/issues/15https://github.com/CntChen/cntchen.github.io/issues/17https…

  • js算法初窥06(算法模式03-函数式编程)

    在解释什么是函数式编程之前,我们先要说下什么是命令式编程,它们都属于编程范式的一种。命令式编程其实就是一块一块的代码,其中包括了我们要执行的逻辑或者判断或者一些运算。也就是按部就班的一步一步完成我们所

  • java中finalized的用法_java中的引用类型

    java中finalized的用法_java中的引用类型我们通常用构造器来创建对象,而Finalize正好相反,构造方法执行对象的初始化操作,finalize方法执行对象的销毁操作.那我们什么时候需要使用finalize方法呢,我们都知道Java里垃圾回收器可以回收对象使用的内存空间,但是对象可能会持有很多资源比如Socket、文件句柄等,垃圾收集器无法回收这些资源,因此你需要使用finalize方法帮助GC回收这些资源,比如关闭打开的文件或者网元资源…

  • 基本数据类型与表达式6 – 零基础入门学习Delphi07

    基本数据类型与表达式6 – 零基础入门学习Delphi07

  • ArcGIS二次开发基础教程(04):有关字段的操作和简单属性及空间查询

    ArcGIS二次开发基础教程(04):有关字段的操作和简单属性及空间查询ArcGIS二次开发基础教程(07):有关字段的操作和简单属性及空间查询属性字段的添加、删除和查找IFeatureLayerGetLayerByName(stringname){ILayerlayer=null;for(inti=0;i<axMapConTrol1.LayerCount;i++){layer=axMapC…

发表回复

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

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