当前位置:网站首页>【HDU】5248-序列变换(贪心+二分)「建议收藏」
【HDU】5248-序列变换(贪心+二分)「建议收藏」
2022-07-07 16:54:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
二分枚举长度改变的长度即可了
#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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116609.html原文链接:https://javaforall.cn
边栏推荐
- 企业展厅设计中常用的三种多媒体技术形式
- 微信网页调试8.0.19换掉X5内核,改用xweb,所以x5调试方式已经不能用了,现在有了解决方案
- SD_ DATA_ RECEIVE_ SHIFT_ REGISTER
- SD_ DATA_ SEND_ SHIFT_ REGISTER
- RISCV64
- 高考填志愿规则
- Classification of regression tests
- Cadre de validation des données Apache bval réutilisé
- Rules for filling in volunteers for college entrance examination
- DeSci:去中心化科学是Web3.0的新趋势?
猜你喜欢
伺服力矩控制模式下的力矩目标值(fTorque)计算
NAT地址转换
6.关于jwt
Skills of embedded C language program debugging and macro use
The performance and efficiency of the model that can do three segmentation tasks at the same time is better than maskformer! Meta & UIUC proposes a general segmentation model with better performance t
线程池和单例模式以及文件操作
Classification of regression tests
idea彻底卸载安装及配置笔记
[paper sharing] where's crypto?
GSAP animation library
随机推荐
不能忽略的现货白银短线操作小技巧
Redis
ip netns 命令(备忘)
[论文分享] Where’s Crypto?
PTA 1102 teaching Super Champion volume
[unity shader] insert pass to realize the X-ray perspective effect of model occlusion
Redis的发布与订阅
Complete e-commerce system
将模型的记忆保存下来!Meta&UC Berkeley提出MeMViT,建模时间支持比现有模型长30倍,计算量仅增加4.5%...
【软件测试】从企业版BOSS直聘,看求职简历,你没被面上是有原因的
虚拟数字人里的生意经
基于图像和激光的多模态点云融合与视觉定位
Do you really understand sticky bag and half bag? 3 minutes to understand it
我感觉被骗了,微信内测 “大小号” 功能,同一手机号可注册两个微信
2022-07-04 matlab读取视频帧并保存
静态路由配置
Cadre de validation des données Apache bval réutilisé
Kubernetes DevOps CD工具对比选型
PTA 1102 教超冠军卷
直播预约通道开启!解锁音视频应用快速上线的秘诀