java练习

心已赠人 2022-04-11 11:13 213阅读 0赞

一、

根据H国的法律，王族的继承顺位这样规定的：

假设A和B是两位王族

1. 如果其中一位是另一位的直系父亲、祖先，则辈份高的王族继承顺位更高

2. 否则，假设C是A和B的最近公共祖先。显然A和B一定是C的两位不同子嗣的后代。其中C较年长的子嗣的后代的继承顺位更高

按时间顺序给出所有国王后代的出生和死亡记录，请你计算所有还活着的后代的继承顺位。

### 输入 ###

第一行包含一个整数N和一个只包含大写字母和数字的字符串，分别代表记录的条数和国王的名字。

以下N行每行包含一条记录：

birth name1 name2 代表name1的儿子name2出生

death name 代表name死亡

1 <= N <= 10000

名字长度不超过20，并且没有重名的王族。

### 输出 ###

按继承顺位从高到低输出每位王族的名字。(不包括国王)

每个名字一行。

### 样例输入 ###

4 KING

birth KING ALI

birth KING BOB

birth ALI CARRO

death ALI

### 样例输出 ###

CARRO

BOB

import java.util.*;
    
    public class Main {
    
    	static Map<String,Queue<String> >son=new HashMap<String,Queue<String>>();
    	static Map<String,Integer> f=new HashMap<String,Integer>();
    	static String root;
    	public static void main(String[] args) {
    		Scanner scan=new Scanner(System.in);
    		int n=scan.nextInt();
    		root=scan.next();
    		for(int i=0;i<n;i++) {
    			String temp=scan.next();
    			if(temp.equals("birth")) {
    				String s1=scan.next();
    				String s2=scan.next();
    				if(son.get(s1)==null) {
    					Queue<String>q=new LinkedList<String>();
    					q.add(s2);
    					son.put(s1, q);
    				}else {
    					son.get(s1).add(s2);
    				}
    			}
    			else if(temp.equals("death")) {
    				String s=scan.next();
    				f.put(s, 1);
    			}	
    		}
    		scan.close();
    		Print(root);
    	}
    	public static void Print(String s) {
    		while(son.get(s)!=null&&!son.get(s).isEmpty()) {
    			String temp=son.get(s).peek();
    			if(f.get(temp)==null&&!temp.equals(root)) {
    				System.out.println(temp);
    			}
    			son.get(s).remove();
    			Print(temp);
    		}
    	}
    }

二、

小Hi的学校正面临着废校的大危机。面对学校的危机，小Hi同学们决定从ABC三个班中各挑出一名同学成为偶像。

成为偶像团体的条件之一，就是3名团员之间的身高差越小越好。

已知ABC三个班同学的身高分别是A1..AN, B1..BM 和 C1..CL。请你从中选出3名同学Ai, Bj, Ck使得D=|Ai-Bj|+|Bj-Ck|+|Ck-Ai|最小。

### 输入 ###

第一行包含3个整数，N, M和L。

第二行包含N个整数，A1, A2, ... AN。(1 <= Ai <= 100000000)

第三行包含M个整数，B1, B2, ... BM。(1 <= Bi <= 100000000)

第四行包含L个整数，C1, C2, ... CL。(1 <= Ci <= 100000000)

对于30%的数据, 1 <= N, M, L <= 100

对于60%的数据，1 <= N, M, L <= 1000

对于100%的数据，1 <= N, M, L <= 100000

### 输出 ###

输出最小的D。

### 样例输入 ###

3 3 3

170 180 190

195 185 175

180 160 200

### 样例输出 ###

import java.util.*;
    import java.math.*;
    public class Main{
    	public static void main(String[] args) {
    		Scanner scan=new Scanner(System.in);
    		int n=scan.nextInt();
    		int m=scan.nextInt();
    		int l=scan.nextInt();
    		int a[]=new int[n];
    		int b[]=new int[m];
    		int c[]=new int[l];
    		for(int i=0;i<n;i++) {
    			a[i]=scan.nextInt();
    		}
    		for(int i=0;i<m;i++) {
    			b[i]=scan.nextInt();
    		}
    		for(int i=0;i<l;i++) {
    			c[i]=scan.nextInt();
    		}
    		Arrays.sort(a);
    		Arrays.sort(b);
    		Arrays.sort(c);
    		int x=1000000001;
    		for(int i=0;i<n;i++) {
    			int t1=halfsort(0,m-1,a[i],b);
    			int t2=halfsort(0,l-1,a[i],c);
    			x=Math.min(x,(Math.abs(a[i]-b[t1])+Math.abs((b[t1]-c[t2]))+Math.abs(c[t2]-a[i])));
    		}
    		System.out.println(x);
    		scan.close();
    	}
    	public static int halfsort(int s,int t,int tar,int a[]) {
    		if(tar>a[t]) {
    			return t;
    		}
    		if(tar<a[s]) {
    			return s;
    		}
    		int temp=(s+t)/2;
    		if(a[temp]==tar)return temp;
    		else if(a[temp]<tar) {
    			s=temp+1;
    		}
    		else if(a[temp]>tar) {
    			t=temp-1;
    		}
    		return halfsort(s,t,tar,a);
    	}
    }