每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数,分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数,分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数,分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。
对于每个小伙伴,在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。
3 3 1 100 10 1000 1000000000 1001 9 10 1000000000
100 1000 1001
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); int m=sc.nextInt(); TreeMap<Integer,Integer> map=new TreeMap<>(); for(int i=0;i<n;i++){ map.put(sc.nextInt(),sc.nextInt()); } int value=0; for(int key:map.keySet()) { if(map.get(key)<value) map.put(key, value); value=map.get(key); } for(int i=0;i<m;i++){ int ai=sc.nextInt(); if(map.floorKey(ai)!=null) System.out.println(map.get(map.floorKey(ai))); else System.out.println(0); } } sc.close(); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int N = sc.nextInt(); int M = sc.nextInt(); //记录难度与报酬的对应关系 TreeMap treeMap = new TreeMap<Integer,Integer>(); for(int i = 0; i < N; i++) { treeMap.put(sc.nextInt(),sc.nextInt()); } //记录M个小伙伴顺序 int[] arr = new int[M]; for(int i = 0; i < M; i++) { Integer temp = sc.nextInt(); if(!treeMap.containsKey(temp)) { //将小伙伴的能力也保存进去 treeMap.put(temp,-1); } arr[i] = temp; } //记录当前难度最大的报酬 int max = 0; Iterator iter = treeMap.entrySet().iterator(); while(iter.hasNext()) { Map.Entry entry = (Map.Entry)iter.next(); max = Math.max(max,(Integer)entry.getValue()); treeMap.put((Integer)entry.getKey(),max); } for(int i = 0; i < M; i++) { System.out.println(treeMap.get(arr[i])); } } } }
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); long d[][]=new long[n][2]; for(int i=0;i<n;i++) { d[i][0]=sc.nextLong(); d[i][1]=sc.nextLong(); } long p[]=new long[m]; for(int i=0;i<m;i++) { p[i]=sc.nextInt(); } long s[]=new long[m]; Arrays.sort(d, new Comparator<long[]>() { @Override public int compare(long[] o1, long[] o2) { // TODO Auto-generated method stub return (int) (o2[1]-o1[1]); } }); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(p[i]>=d[j][0]) { s[i]=d[j][1]; break; } } System.out.println(s[i]); } } }复杂度过大,只通过80%,求改进建议。。。。。。。。。
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n, m; int[] a; List<int[]> dps = new ArrayList<>(); n = in.nextInt(); m = in.nextInt(); a = new int[m]; for(int i = 0; i < n; i++){ int d = in.nextInt(); int p = in.nextInt(); dps.add( new int[]{d, p} ); } for(int i = 0; i < m; i++){ a[i] = in.nextInt(); } /** * 1. 构造集合dps,dps[i] = int[]{d,p}, 难度d, 对应的最大报酬p * 2. 对于每一个输入的能力值,使用二分法查找对应的最大报酬 */ dps.sort(Comparator.comparingInt(o -> o[0])); int max = 0; for(int i=0; i<n; i++){ int[] pair = dps.get(i); //最大报酬 if(pair[1] > max){ max = pair[1]; } pair[1] = max; dps.set(i, pair); } for(int i=0; i<m; i++){ int[] pair = new int[2]; pair[0] = a[i]; //不存在时返回 -(insertion point) - 1 , insertion point 是插入位置 int index = Collections.binarySearch(dps, pair, Comparator.comparingInt(o -> o[0])); if(index < 0){ index++; index = -index; index--; //index = -index-2; } if(index < 0){ System.out.println(0); }else{ System.out.println(dps.get(index)[1]); } } } }
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner read=new Scanner(System.in); int N,M; N=read.nextInt(); M=read.nextInt(); int[] difficulty=new int[N]; int[] pay=new int[N]; int[] powr=new int[M]; for(int i=0;i<N;i++) { difficulty[i]=read.nextInt(); pay[i]=read.nextInt(); } for(int i=0;i<M;i++) { powr[i]=read.nextInt(); } for(int i=N-1;i>0;i--) { int a,b; for(int j=i-1;j>=0;j--) { if(difficulty[i]<difficulty[j]) { a=difficulty[i]; difficulty[i]=difficulty[j]; difficulty[j]=a; b=pay[i]; pay[i]=pay[j]; pay[j]=b; } } } for(int i=0;i<M;i++) { for(int j=N-1;j>=0;j--) { if(powr[i]>=difficulty[j]) { int a1=pay[j]; for(int i1=j-1;i1>=0;i1--) { if(a1<pay[i1]) { a1=pay[i1]; } } System.out.println(a1); break; } } } } }
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { int n = 0;//工作 int m = 0;//人 Map work = new HashMap(); Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); int[] people = new int[m]; int[] pay = new int[m]; for (int i = 0; i < n; i++) { int diff = scanner.nextInt();//难度 int salary = scanner.nextInt();//报酬 work.put(salary, diff); } for (int k = 0; k < m; k++) { final int tmp = scanner.nextInt(); people[k] = tmp; Object obj = work.entrySet().stream().filter(entry -> (int) ((HashMap.Entry) entry).getValue() <= tmp).sorted((o1, o2) -> { if ((int) ((HashMap.Entry) o1).getKey() > (int) ((HashMap.Entry) o2).getKey()) { return -1; } else { return 1; } }).findFirst().get(); pay[k] = (int) ((HashMap.Entry) obj).getKey(); } for (int a : pay) { System.out.println(a); } } }
import java.util.*; public class Main { public static void main(String[] args){ Scanner input = new Scanner(System.in); int N = input.nextInt(); int M = input.nextInt(); int i = 0; int[][] DP = new int[N][2]; for (i = 0;i<N;i++){ DP[i][0] = input.nextInt(); DP[i][1] = input.nextInt(); } TreeMap map = new TreeMap(); //把DP按照第一列排序。 Arrays.sort(DP,(e1,e2) ->(int)(e1[0] - e2[0])); for (i = 1; i<DP.length;i++){ DP[i][1] = Math.max(DP[i-1][1], DP[i][1]); //更新每个难度值对应的报酬为不高于其难度值的所有报酬中最高的报酬。 } for (i = 0; i < DP.length;i++){ map.put(DP[i][0],DP[i][1]); } for (i = 0;i<M;i++){ int ability = input.nextInt(); Integer index = (Integer) map.floorKey(ability); if (index != null) System.out.println(map.get(index)); else System.out.println(0); } } }
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//工作量 int m = sc.nextInt();//小伙伴的个数 //接下来就应该把接受到的信息,放到集合里 TreeMap<Integer,Integer> map1 = new TreeMap<>(); //因为不会输出相同的,所以不用判断 for(int i = 0;i < n;i++){ //直接对应键的最大值 int Di = sc.nextInt(); int Pi = sc.nextInt(); if(map1.containsKey(Di)){ if(Pi > map1.get(Di)){ map1.put(Di,Pi); } } else{ map1.put(Di,Pi); } } TreeMap<Integer,Integer> map2 = new TreeMap<>(); //只能得到key最小的key-value Map.Entry<Integer,Integer> firstEntry = map1.firstEntry(); //并把它放到map2,map2里面存的最佳的工作能力,(1,1000)和(10,100),那么map2里面会存(1,1000),因为一个工作,可以很多个人做 map2.put(firstEntry.getKey(),firstEntry.getValue()); for( Map.Entry<Integer,Integer> f : map1.entrySet()){ //System.out.println(f.getKey()+"---"+f.getValue()); if(f.getValue() > firstEntry.getValue()){ map2.put(f.getKey(),f.getValue()); firstEntry = f; } } for(int i = 0; i< m;i++){ int friend = sc.nextInt(); //返回小于等于给定的key的key-value //此时的map2里面已经是唯一的,一个键一个最大值 Map.Entry<Integer,Integer> floorEntry = map2.floorEntry(friend); if(floorEntry != null){ System.out.println(floorEntry.getValue()); }else{ System.out.println(0); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner( System.in ); //用TreeMap按能力值自动排号序 TreeMap<Integer,Integer> map = new TreeMap<>( ); while(cin.hasNext()) { map.clear(); int n = cin.nextInt(); int m = cin.nextInt(); for(int i=0;i<n;i++) { int d = cin.nextInt(); int p = cin.nextInt(); map.put( d,p ); } //定义一个最小值 int Max = 0x80000000; //遍历 Iterator it = map.keySet().iterator(); while (it.hasNext()) { Integer key = (Integer) it.next(); Integer value = map.get(key); //如果大于最小值,就存下来 if(value>=Max) Max = value; //如果小于 直接替换即可 else map.put(key,Max ); } for(int i=0;i<m;i++) { int a = cin.nextInt(); //找到小于或等于key(a)的最大键 如果不存在就赋值为null Map.Entry<Integer, Integer> result = map.floorEntry(a); if(result==null) System.out.println(0); else System.out.println( result.getValue() ); } } } }
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// int N=3;
// int M=3;
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int M=sc.nextInt();
int[][] nArray=new int[N][2];
for(int i=0;i<nArray.length;i++)
{
for(int j=0;j<nArray[i].length;j++)
{
nArray[i][j]=sc.nextInt();
}
}
int[] mArray=new int[M];
for(int i=0;i<mArray.length;i++)
{
mArray[i]=sc.nextInt();
}
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nArray.length;i++)
{
// for(int j=0;j<nArray[i].length;j++)
// {
map.put(nArray[i][1], nArray[i][0]);
// }
}
for(int j=0;j<mArray.length;j++)
{
int maxNum=0;
int temp=0;
for(Map.Entry<Integer, Integer> tempMap: map.entrySet())
{
if(tempMap.getValue()<=mArray[j])
{
temp=tempMap.getKey();
if(maxNum<temp)
{
maxNum=temp;
}
}
}
System.out.print(maxNum+" ");
}
}
}
大思路:定义一个Job类,再定义一个比较器,先按难度从低到高排列,难度相同的,由报酬从高到底排列。然后排序输入的job数组,难度不同的,去掉报酬低难度高的元素;难度相同的,去掉报酬低的工作,把这些元素都加到TreeMap里面。最后再用小伙伴数组每次查TreeMap的floorKey,如果为null,则不能找到工作,返回0;如果不为null,获取key对应的value就是最高报酬。
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; import java.util.TreeMap; public class Main { //Job类 static class Job { int hard; int money; public Job(int hard, int money) { this.hard = hard; this.money = money; } } //Job比较器,先按难度从低到高排列,难度相同的,由报酬从高到底排列 public static class JobComparator implements Comparator<Job> { public int compare(Job job1, Job job2) { return (job1.hard != job2.hard) ? (job1.hard - job2.hard) : (job2.money - job1.money); } } public static void process(Job[] job, int[] friends) { if (job.length < 1 || friends.length < 1) { return; } //排序job数组,难度不同的,去掉报酬低难度高的元素;难度相同的,去掉报酬低的工作,把这些元素都加到TreeMap里面 Arrays.sort(job, new JobComparator()); TreeMap<Integer, Integer> map = new TreeMap<>(); map.put(job[0].hard, job[0].money); Job pre = job[0]; for (int i = 1; i < job.length; ++i) { if (job[i].hard != pre.hard && job[i].money > pre.money) { pre = job[i]; map.put(job[i].hard, job[i].money); } } // 小伙伴数组每次查TreeMap的floorKey,如果为null,则不能找到工作,返回0;如果不为null,获取key对应的value就是最高报酬 for (int i = 0; i < friends.length; ++i) { if (map.floorKey(friends[i]) == null) { System.out.println(0 + " "); } else { System.out.println(map.get(map.floorKey(friends[i])) + " "); } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); Job[] jobs = new Job[n]; for (int i = 0; i < n; ++i) { int hard = sc.nextInt(); int money = sc.nextInt(); jobs[i] = new Job(hard, money); } int[] friends = new int[m]; for (int i = 0; i < m; ++i) { friends[i] = sc.nextInt(); } //调用主方法 process(jobs, friends); } }
程序通过率只有40%,我注释了大概的思路,求大神们帮忙看看!public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Map<Integer,Integer> map = new HashMap<Integer, Integer>(); int n = Integer.parseInt(scanner.next()); int m = Integer.parseInt(scanner.next()); if (m == 0||n == 0){ System.out.println(0); return; } int[] job = new int[2*n]; int[] power = new int[m]; int i; for (i = 0;i<2*n;i++) job[i] = Integer.parseInt(scanner.next()); for (i = 0;i<2*n;i+=2) //此处,因为题中说保证薪资不会出现相同的情况,所以我把薪资作为hashmap的键,对应的值为相应工作需要的能力 map.put(job[i+1],job[i]); int j; for ( j = 0;j<m;j++) power[j] = Integer.parseInt(scanner.next()); j = 0; Set<Integer> set = map.keySet();//因为hashmap的键是薪资,所以获取hashmap的键的set集合 Object[] salary = set.toArray();//set集合转数组,用数组工具类排序,即把薪资排序 Arrays.sort(salary); while(j<power.length){ Integer max = null; for (i = salary.length-1;i>=0;i--){ if (map.get(salary[i])<=power[j]){ //薪资数组已经由小到大排好序,先求最大薪资对应的工作难度并比较,当遇到第一个小与等于当前人的能力值的,退出循环并输出 max = (Integer) salary[i]; break; } } System.out.println(max); j++; } } }
//思路是对的,简单粗暴,超时了。ggimportjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[] args){Scanner sc=newScanner(System.in);intjob=sc.nextInt();intfri=sc.nextInt();int[] jobD=newint[job];int[] jobS=newint[job];int[] friD=newint[fri];// int[] friMS=new int[fri];for(inti=0;i<job;i++){jobD[i]=sc.nextInt();jobS[i]=sc.nextInt();}for(inti=0;i<fri;i++){friD[i]=sc.nextInt();}for(inti=0;i<fri;i++){inttmp=0;// int tmpC=0;for(intj=0;j<job;j++){if(friD[i]>=jobD[j]){if(tmp<jobS[j]){tmp=jobS[j];// tmpC=j;}}}// friMS[i]=jobS[tmpC];System.out.println(tmp);}// for(int i=0;i<fri;i++){// System.out.println(friMS[i]);// }}}