习题:Wormhole(思路题)
tyvj1763
描述
一维的世界就是一个数轴。这个世界的狭小我们几乎无法想象。
在这个数轴上,有N个点。从左到右依次标记为点1到N。第i个点的坐标为Xi。经过漫长时间的物理变化和化学变化,这个一维世界中产生了一个高等智慧文明,而这N个点都成为了这个文明的一座城市。而点1则成为了这个文明的首都。
出于政治上和经济上的需要,首都不能和任何城市相距太远。所以政府决定在某两个城市耗巨资修建虫洞。一个修建了虫洞的城市可以瞬移到另一个修建了虫洞的城市,从而大大缩短了N个城市相互之间的距离。原先从任意城市i到城市j的路程等于它们的距离|Xi - Xj|,而现在若两个城市附近都有修建了虫洞的城市,则可以先从i移动到附近的虫洞瞬移到城市j附近的虫洞再移动到j。
政府希望在两个合适的城市修建虫洞,使得修建虫洞以后从点1移动到任意城市经过的最短路程的最大值尽量小。请你计算这个路程的最小值是多少。
输入包含多组数据。
格式
输入格式
第一行包括一个正整数T,表示有T组测试数据。接下来依次是T组测试数据。
每组测试数据的第一行包括一个整数N,表示有N个城市。第二行,N个递增的整数,依次表示N个城市的坐标。
输出格式
输出文件包括T行,每行一个整数,依次表示每组测试数据的答案。
样例1
样例输入1[复制]
2
3
0 1 21
5
0 100 101 102 103
样例输出1[复制]
1
2
限制
1s
提示
30%的数据满足:2 <= N <= 200.
60%的数据满足:2 <= N <= 2000.
100%的数据满足:2 <= N <= 200,000, 1 <= T <= 5, |Xi| <= 10^9.
习题:
ans=max(max(cost[i],f[i+1]+g[j])) i=1..n-1
期中cost[i]为i到1的距离,f[i]为i到n所有点进入该范围内某个虫洞的最短时间,g[j]表示以j为另一个虫洞,j到1距离,
显然当j=1时最优
故变为
ans=max(max(cost[i],f[i+1])) i=1..n-1
然后倒着求出f[i],枚举i即可。
代码:
program t1;
var
a:array[..]of longint;
n,i,m,v,u,l,j,ans,t:longint;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(t);
for l:= to t do
begin
readln(n); ans:=maxlongint;
for i:= to n do read(a[i]);
j:=n;
for i:=n downto do
begin
while (a[n]-a[j]<=a[j]-a[i])and(j>i) do dec(j);
v:=max(a[n]-a[j],a[j]-a[i]);
if j=n then u:=maxlongint div else u:=max(a[n]-a[j+],a[+j]-a[i]);
if v>u then begin v:=u; inc(j); end;
v:=max(a[i-]-a[],v);
if v<ans then ans:=v;
end;
writeln(ans);
end;
end.
最新文章
- ActiveMQ的集群方案对比及部署
- 用JAVA实现插值查询的方法(算近似值,区间求法)
- php实现设计模式之 单例模式
- spring-boot 热部署 intellij IDE
- LeetCode 7 Reverse Integer int:2147483647-2147483648 难度:2
- 使用GitHub for Windows客户端管理京东代码库项目
- mysql中IFIND_IN_SET和like的区别
- RunLoop机制理解
- 核反应堆[HDU2085]
- Swift语言实战晋级-第9章 游戏实战-跑酷熊猫-1
- 用c#读取并分析sql2005日志
- Activity之间的跳转
- DecimalFormat(用于格式化十进制数字)
- [转]Blue Prism Interview Questions and Answers
- 恢复数据库的redo日志文件(由于异常关机引起)
- C# array与arraylist区别及获取sql字段名
- postMan测试https接口
- 金三银四季来了!Java 面试题大放送,能答对70%就去BATJTMD试试~
- C程序设计语言习题(1-12)
- jQuery的2把利器
热门文章
- 【洛谷3759】[TJOI2017] 不勤劳的图书管理员(树套树)
- Angular2--显示数据
- 2018.6.13 Java语言基础复习总结
- 2018.5.21 . XMLSpy激活的方法
- MRCA|Wright–Fisher population genetic model|SNP rate
- iOS多播Delegate类——GCDMulticastDelegate用法小结
- redis redis-cli 操作指令
- goaccess 安装
- 一次完整的HTTP请求需要的7个步骤
- Hive如何根据表中某个字段动态分区