欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2017年第八届蓝桥杯Java本科B组国赛题解

程序员文章站 2024-02-10 16:35:10
...

第一题

标题:平方十位数

由0~9这10个数字不重复、不遗漏,可以组成很多10位数字。 这其中也有很多恰好是平方数(是某个数的平方)。

比如:1026753849,就是其中最小的一个平方数。

请你找出其中最大的一个平方数是多少?

注意:你需要提交的是一个10位数字,不要填写任何多余内容。

代码

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	//0-9下标位置分别存储数字0-9
	static int[] a=new int[10];
	static int[] vis=new int[10];//访问标记数组
	public static void dfs(int index)
	{
		//已组成一个10位数字,进行判断是否是平方数
		if(index==10)
		{
			String s="";
			for(int i=0;i<=9;i++)
				s+=a[i];
			long num=Long.parseLong(s);
			long temp=(long)Math.sqrt(num);
			if(temp*temp==num)
			{
				System.out.println(num);
				System.exit(0);
			}
		}
		//a[0]从9开始填,更快找到最大平方数
		for(int i=9;i>=0;i--)
		{
			if(vis[i]==0)
			{
				vis[i]=1;
				a[index]=i;
				dfs(index+1);
				vis[i]=0;
			}
		}
	}
	public static void main(String[] args)
	{
		dfs(0);
	}
}

结果:9814072356

第二题

标题:生命游戏
康威生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
这个游戏在一个无限大的2D网格上进行。

初始时,每个小方格中居住着一个活着或死了的细胞。
下一时刻每个细胞的状态都由它周围八个格子的细胞状态决定。

具体来说:

  1. 当前细胞为存活状态时,当周围低于2个(不包含2个)存活细胞时, 该细胞变成死亡状态。(模拟生命数量稀少)
  2. 当前细胞为存活状态时,当周围有2个或3个存活细胞时, 该细胞保持原样。
  3. 当前细胞为存活状态时,当周围有3个以上的存活细胞时,该细胞变成死亡状态。(模拟生命数量过多)
  4. 当前细胞为死亡状态时,当周围有3个存活细胞时,该细胞变成存活状态。 (模拟繁殖)

当前代所有细胞同时被以上规则处理后, 可以得到下一代细胞图。按规则继续处理这一代的细胞图,可以得到再下一代的细胞图,周而复始。
例如假设初始是:(X代表活细胞,.代表死细胞)

.....
.....
.XXX.
.....

下一代会变为:

.....
..X..
..X..
..X..
.....

康威生命游戏中会出现一些有趣的模式。例如稳定不变的模式:

....
.XX.
.XX.
....

还有会循环的模式:

......      ......       ......
.XX...      .XX...       .XX...
.XX...      .X....       .XX...
...XX.   -> ....X.  ->   ...XX.
...XX.      ...XX.       ...XX.
......      ......       ......

本题中我们要讨论的是一个非常特殊的模式,被称作"Gosper glider gun":

......................................
.........................X............
.......................X.X............
.............XX......XX............XX.
............X...X....XX............XX.
.XX........X.....X...XX...............
.XX........X...X.XX....X.X............
...........X.....X.......X............
............X...X.....................
.............XX.......................
......................................

假设以上初始状态是第0代,请问第1000000000(十亿)代一共有多少活着的细胞?

注意:我们假定细胞机在无限的2D网格上推演,并非只有题目中画出的那点空间。 当然,对于遥远的位置,其初始状态一概为死细胞。

注意:需要提交的是一个整数,不要填写多余内容。

代码

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
//11*38
public class Main {
	static char[][] map=new char[41][68];//存储本次细胞存活情况
	static char[][] next=new char[41][68];//存储下次细胞推演存活情况
	static int n=41,m=68,precount=0,daishu=0;
	static int[][] dir= {{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};//8个方向
	public static void dfs(int x,int y)
	{
		//所有网格细胞存活情况已推演完,即到达(n,0)位置
		if(x==n&&y==0)
		{
			//统计这一代细胞存活数
			int count=0;
			for(int i=0;i<n;i++)
				for(int j=0;j<m;j++)
				{
					if(next[i][j]=='X') count++;
				}
			daishu++;
			System.out.println("第"+daishu+"代存活细胞数:"+count+",比上一代增加了"+(count-precount));
			precount=count;//这一代细胞存活数将变为下一代的前一代
			return;
		}
		//统计该点周围8个方向存活细胞个数
		int sum=0;
		for(int i=0;i<8;i++)
		{
			int newx=x+dir[i][0];
			int newy=y+dir[i][1];
			//如果不是边界且该点细胞为存活状态,则sum++
			if(newx>=0&&newx<n&&newy>=0&&newy<m&&map[newx][newy]=='X') sum++;	
		}
		//推演条件
		if(map[x][y]=='X'&&sum<2) next[x][y]='.';
		else if(map[x][y]=='X'&&sum>3) next[x][y]='.';
		else if(map[x][y]=='.'&&sum==3) next[x][y]='X';
		else
			next[x][y]=map[x][y];
		//一行行逐个点推演,如果纵坐标到边界则从下一行起始位置开始,否则横向逐个推演
		if(y+1>=m) dfs(x+1,0);
		else dfs(x,y+1);
	}
	public static void main(String[] args) throws FileNotFoundException
	{
		//文件输入流
		File file=new File("C:/Users/***/Desktop/data.txt");
		Scanner scan=new Scanner(file);
		//初始化map矩阵
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				map[i][j]='.';
			}
		//读取文件每一行,转换为char数组,存放到map矩阵的中间位置
		int k=0;//改变行数
		while(scan.hasNext())
		{
			char[] c=scan.next().toCharArray();
			for(int j=15;j<=52;j++)
			{
				map[k+15][j]=c[j-15];
				//统计初始状态存活细胞数量
				if(c[j-15]=='X') precount++;
			}
			k++;
		}
		scan.close();
		System.out.println("第0代存活细胞数:"+precount);
		//for循环推演100代(0-99代)
		for(int i=1;i<100;i++)
		{
			dfs(0,0);//从(0,0)位置处开始推演
			for(int j=0;j<n;j++)
				for(int w=0;w<m;w++)
				{
					//下一代推演情况存在next中,需将其赋给map,才能继续推演下一代
					map[j][w]=next[j][w];
				}
		}
	}
}

2017年第八届蓝桥杯Java本科B组国赛题解2017年第八届蓝桥杯Java本科B组国赛题解
从中可以看出规律,每30代循环一次,每次循环增加5,1000000000/30就是循环的次数,也就是增加5的个数,1000000000%30=10,需要再次加上第1-10代的数量变化,算出来是12,同时不要忘记加上初始状态的细胞存活数36,最后的结果就是
36+1000000000/30*5+12=166666713

第三题

标题:树形显示
对于分类结构可以用树形来形象地表示。比如:文件系统就是典型的例子。
树中的结点具有父子关系。我们在显示的时候,把子项向右缩进(用空格,不是tab),并添加必要的连接线,以使其层次关系更醒目。
下面的代码就是为了这个目的的,请仔细阅读源码,并填写划线部分缺少的代码。

import java.util.*;
class MyTree
{
	private Map<String, List<String>>  map_ch = new HashMap<String, List<String>>();
	private Map<String,String> map_pa = new HashMap<String,String>();
	
	public void add(String parent, String child)
	{
		map_pa.put(child, parent);
		
		List<String> lst = map_ch.get(parent);
		if(lst==null){
			lst = new ArrayList<String>();
			map_ch.put(parent, lst);
		}
		lst.add(child);
	}
	
	public String get_parent(String me){
		return map_pa.get(me);
	}
	
	public List<String> get_child(String me){
		return map_ch.get(me);
	}
	
	private String space(int n)
	{
		String s = "";
		for(int i=0; i<n; i++) s += ' ';
		return s;
	}
	
	private boolean last_child(String x){
		String pa = map_pa.get(x);
		if(pa==null) return true;
		
		List<String> lst = map_ch.get(pa);
		return lst.get(lst.size()-1).equals(x);
	}
	
	public void show(String x){
		
		String s = "+--" + x;
		
		String pa = x;
		while(true){
			pa = map_pa.get(pa);
			if(pa==null) break;
			s = ___________________________________ ;  // 填空
		}
		
		System.out.println(s);
	}
	
	public void dfs(String x){
		show(x);
		
		List<String> lst = map_ch.get(x);
		if(lst==null) return;
				
		for(String it: lst){
			dfs(it);
		}
	}
}
 
 
public class TreeView
{
	public static void main(String[] args)
	{
		MyTree tree = new MyTree();
		tree.add("root", "dog");
		tree.add("root", "cat");
		tree.add("root", "duck");
		tree.add("dog", "AAdog");
		tree.add("dog", "BBdog");
		tree.add("dog", "CCdog");
		tree.add("AAdog", "AAdog01");
		tree.add("AAdog", "AAdog02");
		tree.add("cat", "XXcat");
		tree.add("cat", "YYcat");
		tree.add("XXcat","XXcat-oo");
		tree.add("XXcat","XXcat-qq");
		tree.add("XXcat-qq", "XXcat-qq-hahah");
		tree.add("duck", "TTduck");
		tree.add("TTduck", "TTduck-001");
		tree.add("TTduck", "TTduck-002");
		tree.add("TTduck", "TTduck-003");
		tree.add("YYcat","YYcat.hello");
		tree.add("YYcat","YYcat.yes");
		tree.add("YYcat","YYcat.me");		
		
		tree.dfs("root");
	}
}

对于题目中的测试数据,输出结果:

+--root
     +--dog
     |    +--AAdog
     |    |    +--AAdog01
     |    |    +--AAdog02
     |    +--BBdog
     |    +--CCdog
     +--cat
     |    +--XXcat
     |    |    +--XXcat-oo
     |    |    +--XXcat-qq
     |    |         +--XXcat-qq-hahah
     |    +--YYcat
     |         +--YYcat.hello
     |         +--YYcat.yes
     |         +--YYcat.me
     +--duck
          +--TTduck
               +--TTduck-001
               +--TTduck-002
               +--TTduck-003

如有平字体对齐问题,可以参见图【p1.png】
2017年第八届蓝桥杯Java本科B组国赛题解
注意,只填写划线部分缺少的代码,不要抄写已有的代码或符号。

填空结果

(last_child(pa)?space(5):"|"+space(4))+s

运行结果如下
2017年第八届蓝桥杯Java本科B组国赛题解
第四题

标题:小计算器
问题描述   
模拟程序型计算器,依次输入指令,可能包含的指令有
  1. 数字:‘NUM X’,X为一个只包含大写字母和数字的字符串,表示一个当前进制的数
  2. 运算指令:‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’,分别表示加减乘,除法取商,除法取余
  3. 进制转换指令:‘CHANGE K’,将当前进制转换为K进制(2≤K≤36)
  4. 输出指令:‘EQUAL’,以当前进制输出结果
  5. 重置指令:‘CLEAR’,清除当前数字
  指令按照以下规则给出:
  数字,运算指令不会连续给出,进制转换指令,输出指令,重置指令有可能连续给出
  运算指令后出现的第一个数字,表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
  重置指令后出现的第一个数字,表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
  进制转换指令可能出现在任何地方
  运算过程中中间变量均为非负整数,且小于2^63。
  以大写的'A'~'Z'表示10~35
输入格式
  第1行:1个n,表示指令数量
  第2…n+1行:每行给出一条指令。指令序列一定以’CLEAR’作为开始,并且满足指令规则
输出格式
  依次给出每一次’EQUAL’得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

代码

import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		scan.nextLine();//接收回车符
		int nowjz=10,op=0,clear=0;
		long result = 0;
		for(int i=0;i<n;i++)
		{
			String s=scan.nextLine();
			if(s.equals("EQUAL"))
			{
				System.out.println(Long.toString(result,nowjz).toUpperCase());
			}
			else if(s.equals("ADD"))
			{
				op=1;
			}
			else if(s.equals("SUB"))
			{
				op=2;
			}
			else if(s.equals("MUL"))
			{
				op=3;
			}
			else if(s.equals("DIV"))
			{
				op=4;
			}
			else if(s.equals("MOD"))
			{
				op=5;
			}
			else if(s.equals("CLEAR"))
			{
				//清空标记
				clear=0;
			}
			else if(s.startsWith("CHANGE"))
			{
				nowjz=Integer.parseInt(s.split(" ")[1]);
				//result=Long.parseLong(String.valueOf(result),nowjz);
			}
			else
			{
				//如果清空标记为0,则下次输入的NUM 即为初始值
				if(clear==0)
				{
					result=Long.parseLong(s.split(" ")[1],nowjz);
					clear=1;
				}
				else
				{
					if(op==1) result+=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==2) result-=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==3) result*=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==4) result/=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==5) result%=Long.parseLong(s.split(" ")[1],nowjz);	
				}
			}
		}
		scan.close();
	}
}

说明:该部分代码只能得到70%的分数,故对输入流进行修改,不再使用效率较低的Scanner,改为使用效率较高的BufferedReader。
2017年第八届蓝桥杯Java本科B组国赛题解
修改后的代码

import java.io.*;
import java.util.*;

public class Main
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
		String ss=reader.readLine();
		long n=Long.parseLong(ss);
		int nowjz=10,op=0,clear=0;
		long result = 0;
		String s=null;
		for(long i=0;i<n;i++)
		{
			s=reader.readLine().trim();
			if(s.equals("EQUAL"))
			{
				System.out.println(Long.toString(result,nowjz).toUpperCase());
			}
			else if(s.equals("ADD"))
			{
				op=1;
			}
			else if(s.equals("SUB"))
			{
				op=2;
			}
			else if(s.equals("MUL"))
			{
				op=3;
			}
			else if(s.equals("DIV"))
			{
				op=4;
			}
			else if(s.equals("MOD"))
			{
				op=5;
			}
			else if(s.equals("CLEAR"))
			{
				//清空标记
				clear=0;
			}
			else if(s.startsWith("CHANGE"))
			{
				nowjz=Integer.parseInt(s.split(" ")[1]);
			}
			else
			{
				//如果清空标记为0,则下次输入的NUM 即为初始值
				if(clear==0)
				{
					result=Long.parseLong(s.split(" ")[1],nowjz);
					clear=1;
				}
				else
				{
					if(op==1) result+=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==2) result-=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==3) result*=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==4) result/=Long.parseLong(s.split(" ")[1],nowjz);
					else if(op==5) result%=Long.parseLong(s.split(" ")[1],nowjz);	
				}
			}
		}
	}
}

提交结果如下:
2017年第八届蓝桥杯Java本科B组国赛题解
第五题

标题: 填字母游戏
问题描述   
小明经常玩 LOL 游戏上瘾,一次他想挑战K大师,不料K大师说:
  “我们先来玩个空格填字母的游戏,要是你不能赢我,就再别玩LOL了”。
  K大师在纸上画了一行n个格子,要小明和他交替往其中填入字母。
  并且:
  1. 轮到某人填的时候,只能在某个空格中填入L或O
  2. 谁先让字母组成了“LOL”的字样,谁获胜。
  3. 如果所有格子都填满了,仍无法组成LOL,则平局。
  小明试验了几次都输了,他很惭愧,希望你能用计算机帮他解开这个谜。
输入格式
  第一行,数字n(n<10),表示下面有n个初始局面。
  接下来,n行,每行一个串,表示开始的局面。
  比如:“******”, 表示有6个空格。“L****”, 表示左边是一个字母L,它的右边是4个空格。
输出格式
  要求输出n个数字,表示对每个局面,如果小明先填,当K大师总是用最强着法的时候,小明的最好结果。
  1 表示能赢
  -1 表示必输
  0 表示可以逼平
样例输入

4
***
L**L
L**L***L
L*****L

样例输出
0
-1
1
1

代码

这道题考虑了很久,也参考了别人很多,但还是没有能够得到满分的代码,下面的代码可以得到60,已经很不容易了,参考:https://blog.csdn.net/listener_yjt/article/details/80342530

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
	static char[] lox = { 'L', 'O', '*' };
	static char[] lxl = { 'L', '*', 'L' };
	static char[] xol = { '*', 'O', 'L' };
 
	static char[] x = { '*' };
 
	/**
	 * 来源于java.lang.String
	 * 
	 * 在source字符数组中查找target字符数组所在位置
	 * 
	 * @param source
	 *            源字符数组
	 * @param sourceOffset
	 *            源数组起始位置
	 * @param sourceCount
	 *            源数组参与查找的字符个数
	 * @param target
	 *            待查找数组
	 * @param targetOffset
	 *            待查找数组起始位置
	 * @param targetCount
	 *            待查找参与的字符个数
	 * @param fromIndex
	 *            查找起始位置
	 * @return 返回第一次出现的第一个字符所在位置,不存在返回-1
	 */
	static int indexOf(char[] source, int sourceOffset, int sourceCount,
			char[] target, int targetOffset, int targetCount, int fromIndex) {
		if (fromIndex >= sourceCount) {
			return (targetCount == 0 ? sourceCount : -1);
		}
		if (fromIndex < 0) {
			fromIndex = 0;
		}
		if (targetCount == 0) {
			return fromIndex;
		}
 
		char first = target[targetOffset];
		int max = sourceOffset + (sourceCount - targetCount);
 
		for (int i = sourceOffset + fromIndex; i <= max; i++) {
			if (source[i] != first) {
				while (++i <= max && source[i] != first)
					;
			}
 
			if (i <= max) {
				int j = i + 1;
				int end = j + targetCount - 1;
				for (int k = targetOffset + 1; j < end
						&& source[j] == target[k]; j++, k++)
					;
 
				if (j == end) {
					return i - sourceOffset;
				}
			}
		}
		return -1;
	}
 
	/**
	 * 回溯试探博弈,暴力**
	 * 
	 * 非常耗时,c++都超时别说是Java,时间复杂度2^n啊
	 * 
	 * 能不能做点优化或者用动态规划实现?
	 * 
	 * @param c
	 * @return
	 */
	static int f(char[] c, short[] jl) {
		// 处处是套路,直接调用肯定不行
		// String s = new String(c);
 
		// 像这种情况应该做个备忘录吧?
		// 查找到数组对应的索引值
		int idx = getJLindex(c);
		if (jl[idx] != 0) {
			if (jl[idx] == 2) {
				return 0;
			}
			return jl[idx];
		}
 
		// 偷API果然省下不少的空间,在运行上也变快了
 
		// 仔细想想,其实对方留下XOL,LXL,LOX这种局面时,必然是赢的
		if (indexOf(c, 0, c.length, lox, 0, 3, 0) != -1) {
			jl[idx] = 1;
			return 1;
		}
 
		if (indexOf(c, 0, c.length, lxl, 0, 3, 0) != -1) {
			jl[idx] = 1;
			return 1;
		}
 
		if (indexOf(c, 0, c.length, xol, 0, 3, 0) != -1) {
			jl[idx] = 1;
			return 1;
		}
 
		// 在序列中找不到可以填的位置了,然后有没形成LOL(能形成的都被上面return了),那肯定平了。
		if (indexOf(c, 0, c.length, x, 0, 1, 0) == -1) {
			jl[idx] = 2;
			return 0;
		}
 
		// if (s.contains("LOL"))
		// return -1;
		// if (s.contains("*") == false)
		// return 0;// 出口勿漏
 
		boolean ping = false;// 假设无法逼平
 
		for (int i = 0; i < c.length; i++) {
			// 每个位置有三种情况L,O,*
			// 这种填法会出现相同的局面,重点是要重复判断,如果能记录下局面,遇到相同局面就立马能判定胜负
			if (c[i] == '*') {
				try {
					c[i] = 'L';// 试探填L
					if (f(c, jl) == -1) {
						jl[idx] = 1;
						return 1;
					} else if (f(c, jl) == 0)
						ping = true; // 不能直接返回0,否则不能进行进一步试探
 
					c[i] = 'O';// 试探填O
					if (f(c, jl) == -1) {
						jl[idx] = 1;
						return 1;
					} else if (f(c, jl) == 0)
						ping = true;
 
				} finally {
					c[i] = '*';// 回溯
				}
			}
		}
 
		if (ping) {
			jl[idx] = 2;
			return 0;
		}
 
		jl[idx] = -1;
		return -1;
	}
 
	/**
	 * 根据数组获得索引值
	 * 
	 * @param c
	 * @return
	 */
	private static int getJLindex(char[] c) {
		int l = c.length;
		int sum = 0;
 
		// 我这里用了类比三进制数的表示法,从00...0到22...2,下标值转成十进制
		// 其中L表示1,O表示2,*则表示0,例如LOL三进制表示121,索引16
		for (int i = 0; i < l; i++) {
			if (c[i] == '*') {
				continue;
			} else if (c[i] == 'L') {
				sum += pow3(i);
			} else {
				//这里是2*3^i的意思
				sum += (pow3(i) << 1);
			}
		}
		return sum;
	}
	
	/**
	 * 求3的k次方
	 * @param num
	 * @param k
	 * @return
	 */
	private static int pow3(int k) {
		int pow = 1;
		for(int i = 1;i <= k;i++) {
			pow = (pow << 1) + pow;
		}
		return pow;
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		// 存储输入的字符串
		String[] str = new String[n];
		for (int i = 0; i < n; i++) {
			str[i] = br.readLine();
		}
 
		for (int i = 0; i < n; i++) {
			int l = str[i].length();
			int len = pow3(l);
			// 用于记录局面所得到的结果,当长度较长时出现OOM(java.lang.OutOfMemoryError)
			// 因为每个位置有三种值,所以没法用boolean表示了,所以开辟了short数组
			// 默认值0用于标识这种局面还没遇过,其它值表示遇到过相同的局面了,1表示胜,2表示平,-1表示负
			short[] record = new short[len];
			System.out.println(f(str[i].toCharArray(), record));
		}
	}
}

第六题

标题:区间移位
问题描述 
数轴上有n个闭区间D1,…,Dn。其中区间Di用一对整数[ai, bi]来描述,满足ai < bi。已知这些区间
的长度之和至少有10000。所以,通过适当的移动这些区间,你总可以使得他们的“并”覆盖[0, 10000]——也就是说[0, 10000]这个区间内的每一个点都落于至少一个区间内。
  你希望找一个移动方法,使得位移差最大的那个区间的位移量最小。
  具体来说,假设你将Di移动到[ai+ci, bi+ci]这个位置。你希望使得maxi |ci|  最小。
输入格式
  输入的第一行包含一个整数n,表示区间的数量。
  接下来有n行,每行2个整数ai,  bi,以一个空格分开,表示区间[ai, bi]。保证区间的长度之和至少是10000。
输出格式
  输出一个数,表示答案。如果答案是整数,只输出整数部分。如果答案不是整数,输出时四舍五入保留一位小数。
样例输入
2
10 5010
4980 9980
样例输出
20
样例说明
  第一个区间往左移动10;第二个区间往右移动20。
样例输入
4
0 4000
3000 5000
5001 8000
7000 10000
样例输出
0.5
样例说明
  第2个区间往右移0.5;第3个区间往左移0.5即可。
数据规模和约定
  对于30%的评测用例,1 ≤ n ≤ 10;
  对于100%的评测用例,1 ≤ n ≤ 10000,0 ≤ ai < bi  ≤ 10000。

代码
参考:https://blog.csdn.net/ffgcc/article/details/88313119

import java.io.*;
import java.util.*;

class S implements Comparable<S>
{
	int l;
	int r;
	public S(int l,int r) {
		this.l=l;
		this.r=r;
	}
	@Override
	public int compareTo(S o) {
		// TODO Auto-generated method stub
		if(this.r!=o.r)
			return (int) (this.r-o.r);
		else {
			return (int) (this.l-o.l);
		}
	}
}

public class Main {
	static int N=20000;
	static S[]s=new S[10100];
	static int []vis=new int [10100];
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int now =0;
		String str=br.readLine();
		for(int i=0;i<str.length();i++) {
			now=now*10+(int)(str.charAt(i)-'0');
		}
		n=now;
		int sum=0;
		
		for(int i=0;i<n;i++) {
			now=0;
			str=br.readLine();
			int a = 0,b;
			for(int j=0;j<str.length();j++) {
				if(str.charAt(j)==' ') {
					a=now;
					now=0;
				}
				else {
					now=now*10+(int)(str.charAt(j)-'0');
				}
			}
			b=now;
			sum+=b-a;
			s[i]=new S(a*2,b*2);
		}
		Arrays.sort(s,0,n);
		int l=0,r=N;
		while(l<=r) {
			int mid=(l+r)/2;
			//System.out.println(mid);
			if(check(mid)==true) {
				r=mid-1;
			}
			else {
				l=mid+1;
			}
		}
		if(l%2==0) {
			System.out.println(l/2);
		}
		else
			System.out.println(((double)(l)*1.0)/2.0);
	}
	static boolean check(int x) {
		int now=0;
		for(int i=0;i<10100;i++) {
			vis[i]=0;
		}
		while(true)
		{
			int flag=0;
		
			int l=0,r=n;
			while(l<=r) {
				int mid=(l+r)/2;
				if(s[mid].r+x>=now) {
					r=mid-1;
				}
				else l=mid+1;
			}
			for(int i=l;i<n;i++) {
				if(s[i].l<=x+now&&vis[i]==0) {
					flag=1;
					vis[i]=1;
					if(now<=s[i].l+x) now+=s[i].r-s[i].l;
					else now =s[i].r+x;
					break;
				}
			}
			if(now>=20000) return true;
			if(flag==0) return false;
		}
	}
}