星际争霸、宝石塔的亮度差异、寻找食物储量
星际争霸
问题描述
在星际争霸的世界中，每个种族都有自己独特的技术和战略。Protoss种族的指挥官们已经研发出了一种新的战略来对抗他们的敌人。
他们有一种叫做 Psionic Matrix 的设备，可以储存并分析战斗数据。这个设备可以记录每个单位的战斗力，这个战斗力被表示为一个正整数。随着战斗的进行，这些战斗力值会被储存在一个数组 aa 中。
现在，指挥官们想要对这些战斗力值进行排序。他们发现，每次在排序过程中更改两个数的位置，都会产生一种 Psionic Disturbance （灵能干扰）。为了尽量减少这种干扰，他们希望按照逆序对的数量进行排序。如果两个数的逆序对数量相同，他们会根据数值的大小进行排序。
请你帮助他们完成这个任务。
输入格式
第一行输入一个正整数 nn，表示数组的长度。
接下来 nn 行每行输入一个正整数 aiai，表示数组 aa 中的第 ii 个元素。
输出格式
输出共 nn 行，每行输出一个整数，表示排序后的数组 aa。
样例输入
5 12 31 45 123 452样例输出
12 45 123 31 452说明
1212 的逆序对数为 00，3131 的逆序对数为 11，4545 的逆序对数为 00，123123 的逆序对数为 00，452452 的逆序对数为 22。
故最终排序结果为 12[0]12[0]，45[0]45[0]，123[0]123[0]，31[1]31[1]，452[2]452[2]，[][] 中的数表示逆序对数。
数据范围
对于 100100% 的数据，1≤n≤10001≤n≤1000，1≤ai≤1010001≤ai≤101000，aiai 可能包含前导 00，输出时请保留前导零。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Main { static Map<Integer, Integer> map=new HashMap<Integer, Integer>(); static int N=10000,idx;//res=0; //static Integer a[]=new Integer[N]; static String stringa[]=new String[N]; static Node node[]=new Node[N]; // static boolean f[]=new boolean[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); //String g[]=br.readLine().split(" "); for (int i = 0; i < n; i++) { String t=br.readLine(); node[i]=new Node(cal(t),t); } Arrays.sort(node,0,n,(Node a,Node b)->{ if(a.revnum==b.revnum){//注意：这里一定不能用字符串比较 e.g 10,2 BigInteger bigInteger1 =new BigInteger(a.num); BigInteger bigInteger2 =new BigInteger(b.num); return bigInteger1.compareTo(bigInteger2); }else{ return Long.compare(a.revnum,b.revnum); } }); for (int i = 0; i < n; i++) { System.out.println(node[i].num); } } static long cal(String n){ long res=0; //BigInteger bigInteger=new BigInteger(n); char c[]=n.toCharArray(); int cnt[]=new int[10];//核心是只有数值0-9 for (int i = 0; i < c.length; i++) { int f=c[i]-'0'; for (int j = f+1; j < 10; j++) { res+=cnt[j]; } cnt[f]++; } return res; } static class Node { long revnum; String num; public Node() { // TODO Auto-generated constructor stub } public Node(long revnum, String num) { this.revnum = revnum; this.num = num; } } }宝石塔的亮度差异
问题描述
丽丽的家里建了两座宝石塔高度为 NN 的宝石塔，宝石塔每一层都有一颗独特的宝石，且宝石的亮度各不相同。
阿鹏决定美化这些宝石。他可以在两个宝石塔的任意两层交换宝石，交换的次数没有限制。他想通过交换，使得他收集到的第一个宝石塔的宝石亮度差异（最亮的宝石的亮度减去最暗的宝石的亮度）尽可能小。
请你帮助阿鹏，找出最小的亮度差异值。
输入格式
第一行输入一个整数 NN（1≤N≤1031≤N≤103），表示两座宝石塔的层数。
第二行输入 NN 个空格分隔的整数 A1,A2,…,ANA1,A2,…,AN（1≤Ai≤1051≤Ai≤105），表示第一个宝石塔每一层宝石的亮度。
第三行输入 NN 个空格分隔的整数 B1,B2,…,BNB1,B2,…,BN（1≤Bi≤1051≤Bi≤105），表示第二个宝石塔每一层宝石的亮度。
输出格式
输出一行，表示最小的亮度差异值。
样例输入
4 2 1 4 3 3 2 6 2样例输出
1import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Main { static Map<Integer, Integer> map=new HashMap<Integer, Integer>(); static int N=2*1010,idx;//res=0; static int a[]=new int[N]; //static int b[]=new int[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); String g[]=br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } g=br.readLine().split(" "); for (int i = 0; i < n; i++) { a[n+i]=Integer.parseInt(g[i]); } Arrays.sort(a,0,2*n); int res=Integer.MAX_VALUE; for (int i = 0; i <= n; i++) { res=Math.min(a[i+n-1]-a[i], res); } System.out.println(res); } }折半搜索
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; public class Main { static Map<Long, Integer> map=new HashMap<>(); static int N=100,idx; static boolean res=false; static long v[]=new long[N]; static long w[]=new long[N]; //static long a[]=new long[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); //int n=Integer.parseInt(br.readLine()); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]); long s=Long.parseLong(g[1]); g=br.readLine().split(" "); int n1=n/2,n2=n-n1; for (int i = 0; i < n1; i++) { v[i]=Long.parseLong(g[i]); //System.out.print(v[i]+" "); } for (int i = 0; i < n2; i++) { w[i]=Long.parseLong(g[n1+i]); //System.out.print(w[i]+" "); } dfs1(0,0,n1); dfs2(0,0,n2,s); if(res==true){ System.out.println("Yes"); }else{ System.out.println("No"); } } static void dfs1(int k,long sum,int n){ if(k>=n){ map.put(sum, map.getOrDefault(sum, 0)+1); return; } dfs1(k+1, sum+v[k], n); dfs1(k+1, sum, n); } static void dfs2(int k,long sum,int n,long s){ if(k>=n){ if(map.containsKey(s-sum))res=true; return; } dfs2(k+1, sum+w[k], n,s); dfs2(k+1, sum, n,s); } }寻找食物储量
问题描述
你是一个冒险家，在一个危机四伏的森林里，你发现了一个隐藏的食物仓库。这个食物仓库由 nn 个房间组成，每个房间都有一定数量的食物。你需要找到第一个房间，其中的食物数量大于或等于一个给定的值 xx。
这些房间是按食物数量升序排列的。你知道每个房间的食物数量，但由于时间紧迫，你不能一个个房间地去查找。因此，你决定使用二分搜索来快速找到目标房间。
你的任务是编写一个程序，根据每个房间的食物数量和目标值 xx，输出第一个食物数量大于或等于 xx 的房间的编号。
输入格式
第一行包含一个整数 nn，(1≤n≤105)(1≤n≤105)，表示房间的数量。
第二行包含 nn 个整数，表示每个房间的食物数量。这些整数是非降序排列的。
第三行包含一个整数 xx，(1≤x≤109)(1≤x≤109)，表示目标食物数量。
输出格式
输出一个整数，表示第一个食物数量大于或等于 xx 的房间的编号。如果所有房间的食物数量都小于 xx，则输出 −1−1。
样例输入
5 2 5 8 10 15 9样例输出
4样例说明
在上述例子中，房间 44 的食物数量为 1010，这是第一个大于或等于 99 的值。
测评数据规模
对于 100100% 的数据，1≤n≤1061≤n≤106，并且每个房间的食物数量不超过 109109。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; public class Main { static Map<Long, Integer> map=new HashMap<>(); static int N=1000010,idx; static boolean res=false; static int a[]=new int[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); String g[]=br.readLine().split(" "); int x=Integer.parseInt(br.readLine()); for (int i = 0; i <n; i++) { a[i]=Integer.parseInt(g[i]); } int l=0,r=n-1; while(l<r){ int mid=(l+r)>>1; if(a[mid]>=x){ r=mid; }else{ l=mid+1; } } if(a[l]>=x){ System.out.println(l+1); }else{ System.out.println(-1); } } }