ABC318 F - Octopus

解题思路

• 对于每个宝藏维护个区间，答案一定在这些区间中
• 对于每个区间的端点由小到大排序
• 对于每个点进行判断，若当前位置合法，则该点一定为一个右端点
• 则该点到前一个端点之间均为合法点
• 若前一个点不合法，则一定是某一个区间限制的左端点，所以该点到这个端点之间均未超出范围，使某一宝藏取不到
• 若前一个点合法，则在满足的前提下，还避免了重复

import java.io.*;
import java.math.BigInteger;
import java.util.*;//implements Runnable
public class Main {static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int N=200010;static int n=0;static int m=0;static long ans=0;static long[] a;static long[] b;static boolean check(long x){PriorityQueue<Long> q=new PriorityQueue<>((o1,o2)->{if(o1-o2>0)return 1;else if(o1-o2<0)return -1;else return 0;});for(int i=1;i<=n;++i){q.add(Math.abs(x-a[i]));}for(int i=1;i<=n;++i){if(q.poll()>b[i])return false;}return true;}static void solve() throws Exception{AReader input=new AReader();
//        String fileName="C:\\Users\\Lenovo\\Downloads\\055.txt";
//		Scanner input=new Scanner(new FileReader(fileName));//        BufferedReader input = new BufferedReader(new FileReader(fileName));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));String al="abcdefghijklmnopqrstuvwxyz";char[] ac=al.toCharArray();n=input.nextInt();a=new long[n+1];for(int i=1;i<=n;++i)a[i]=input.nextLong();b=new long[n+1];for(int i=1;i<=n;++i)b[i]=input.nextLong();Arrays.sort(b,1,n+1);TreeSet<Long> hs=new TreeSet<>();for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){hs.add(a[i]-b[j]-1);//左端点，左开右闭，区分左端点和右端点hs.add(a[i]+b[j]);//右端点}}long l=0;for(long x:hs){if(check(x))ans+=x-l;l=x;//左端点,要么是右端点区间去重叠}out.println(ans);out.flush();out.close();}public static void main(String[] args) throws Exception{solve();}//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Tx2(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}staticclass AReader{BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}