BC 2015在百度之星程序设计大赛 - 预赛(1)(系列转换-二分法答案贪婪)

简介:

系列转换

Accepts: 816
Submissions: 3578
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description

给定序列A={A 1 ,A 2 ,...,A n } , 要求改变序列A中的某些元素,形成一个严格单调的序列B(严格单调的定义为:B i <B i+1 ,1i<N )。

我们定义从序列A到序列B变换的代价为cost(A,B)=max(|A i B i |)(1iN) 

请求出满足条件的最小代价。

注意,每一个元素在变换前后都是整数。

Input

第一行为測试的组数T(1T10) .

对于每一组: 第一行为序列A的长度N(1N10 5 ) ,第二行包括N个数,A 1 ,A 2 ,...,A n  . 序列A中的每一个元素的值是正整数且不超过10 6  

Output

对于每个測试例子,输出两行:

第一行输出:"Case #i:"。

i代表第 i 组測试数据。

第二行输出一个正整数,代表满足条件的最小代价。

Sample Input
2
2
1 10
3
2 5 4
Sample Output
Case #1:
0
Case #2:
1

二分答案,每一个数贪最小



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<queue>
#include<vector>
#include<deque>
#include<complex>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (100000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int a[MAXN],n;
bool is_ok(int c)
{
	int p=a[1]-c;
	Fork(i,2,n)
	{
		if (a[i]>p)
		{
			p=max(a[i]-c,p+1);
		}
		else
		{
			if (a[i]+c<=p) return 0;
			else p=min(a[i]+c,p+1);
		}
	}	
	
	
	
	return 1;
}
int main()
{
//	freopen("seq.in","r",stdin);
//	freopen(".out","w",stdout);
	
	int T;
	cin>>T;
	For(kcase,T)
	{
		cin>>n;
		For(i,n) scanf("%d",&a[i]); 
		
		ll l=0,r=F,ans=r,m=-1;
		while (l<=r)
		{
			m=(l+r)/2;
			if (!is_ok(m)) l=m+1;
			else r=m-1,ans=m; 
		}
		
		
		
		printf("Case #%d:\n",kcase);
		cout<<ans<<endl;
	}
	
	
	
	return 0;
}






版权声明:本文博主原创文章,博客,未经同意不得转载。





本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4909389.html,如需转载请自行联系原作者


相关文章
|
Linux 数据安全/隐私保护 Windows
更换(Pypi)pip源到国内镜像
pip国内的一些镜像 阿里云 http://mirrors.aliyun.com/pypi/simple/ 中国科技大学 https://pypi.mirrors.
244570 2
|
Docker 容器
Docker 容器中运行 Kibana
Docker 容器中运行 Kibana
274 0
|
运维 监控 安全
阿里云香港轻量应用服务器评测,1核1G 30M 24元/月,低价VPS
阿里云香港轻量应用服务器评测,1核1G 30M 24元/月,低价VPS
5301 0
|
云安全 安全 网络安全
【阿里云资讯】阿里云电子政务云平台首批通过党政部门云服务网络安全审查
9月19日,在2016年国家网络安全宣传周上,中央网信办宣布,经过多轮评议,阿里云电子政务云平台通过党政部门云计算服务网络安全审查(增强级)。 据悉,阿里云提供的电子政务云平台首批参与党政部门云计算服务网络安全审查的服务商。
4155 0
|
20天前
|
存储 人工智能 测试技术
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
141061 20
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
|
19天前
|
人工智能 运维 前端开发
基于阿里百炼的DeepSeek-R1满血版模型调用【零门槛保姆级2084小游戏开发实战】
本文介绍基于阿里百炼的DeepSeek-R1满血版模型调用,提供零门槛保姆级2048小游戏开发实战。文章分为三部分:定位与核心优势、实战部署操作指南、辅助实战开发。通过详细步骤和案例展示,帮助开发者高效利用DeepSeek-R1的强大推理能力,优化游戏逻辑与视觉效果,解决官网响应延迟问题,提升开发效率和用户体验。适合企业开发者、教育行业及多模态探索者使用。
70896 17
基于阿里百炼的DeepSeek-R1满血版模型调用【零门槛保姆级2084小游戏开发实战】
|
27天前
|
人工智能 自然语言处理 Shell
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
仅用3分钟,百炼调用满血版Deepseek-r1 API,享受百万免费Token。阿里云提供零门槛、快速部署的解决方案,支持云控制台和Cloud Shell两种方式,操作简便。Deepseek-r1满血版在推理能力上表现出色,尤其擅长数学、代码和自然语言处理任务,使用过程中无卡顿,体验丝滑。结合Chatbox工具,用户可轻松掌控模型,提升工作效率。阿里云大模型服务平台百炼不仅速度快,还确保数据安全,值得信赖。
358007 62
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
|
23天前
|
人工智能 自然语言处理 API
快速使用 DeepSeek-R1 满血版
DeepSeek是一款基于Transformer架构的先进大语言模型,以其强大的自然语言处理能力和高效的推理速度著称。近年来,DeepSeek不断迭代,从DeepSeek-V2到参数达6710亿的DeepSeek-V3,再到性能比肩GPT-4的DeepSeek-R1,每次都带来重大技术突破。其开源策略降低了AI应用门槛,推动了AI普惠化。通过阿里云百炼调用满血版API,用户可以快速部署DeepSeek,享受高效、低成本的云端服务,最快10分钟完成部署,且提供免费token,极大简化了开发流程。
191001 23
快速使用 DeepSeek-R1 满血版
|
8天前
|
人工智能 搜索推荐 数据可视化
Manus:或将成为AI Agent领域的标杆
随着人工智能技术的飞速发展,AI Agent(智能体)作为人工智能领域的重要分支,正逐渐从概念走向现实,并在各行各业展现出巨大的应用潜力。在众多AI Agent产品中,Manus以其独特的技术优势和市场表现,有望成为该领域的标杆。作为资深AI工程师,本文将深入探讨Manus的背景知识、主要业务场景、底层原理、功能的优缺点,并尝试使用Java搭建一个属于自己的Manus助手,以期为AI Agent技术的发展和应用提供参考。
11061 13
|
8天前
|
机器学习/深度学习 人工智能 测试技术
阿里云百炼已上线超强推理开源模型QwQ-32B,尺寸更小,性能比肩DeepSeek满血版
通义千问团队推出了320亿参数的QwQ-32B模型,通过大规模强化学习和多阶段训练,在数学、编程及通用能力上达到或超越了DeepSeek-R1等先进模型。QwQ-32B模型已在阿里云百炼上线,支持API调用,用户可通过官方文档了解详细使用方法。未来,团队将继续探索智能体与RL集成,推动人工通用智能的发展。