1、排序
算法分析
用结构体存储，并进行排序
时间复杂度 )
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int N = 110;
static Pair[] pair = new Pair[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
int s = scan.nextInt();
pair[i] = new Pair(i,s);
}
Arrays.sort(pair,1,n + 1);
for(int i = n;i >= 1;i --)
{
if(i != 1) System.out.print(pair[i].id + " ");
else System.out.println(pair[i].id);
}
}
}
class Pair implements Comparable<Pair>
{
int id,s;
Pair(int id ,int s)
{
this.id = id;
this.s = s;
}
@Override
public int compareTo(Pair o) {
// TODO 自动生成的方法存根
return Integer.compare(s, o.s);
}
}
2、成绩排序
算法分析
先对分数从小到大排序，分数相同的情况下对字符串从大到小排序
这里有两种需要排序，优先分数，分数相同，字典序小优先
- 1、分数排序
- 2、分数相同，字符串排序 a.compareTo(b)，sort一遍，会从小到大排好
时间复杂度
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int N = 110;
static int n;
static Pair[] pair1 = new Pair[N];
static Pair[] pair2 = new Pair[N];
static Pair[] pair3 = new Pair[N];
static Pair[] pair4 = new Pair[N];
static Pair[] pair5 = new Pair[N];
static void print(Pair[] pair)
{
Arrays.sort(pair,0,n);
for(int i = n - 1,j = 0;j != 4;i --,j ++)
{
if(j != 3) System.out.print(pair[i].name + " ");
else System.out.println(pair[i].name);
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 0;i < n;i ++)
{
String s = scan.next();
int a = scan.nextInt();
int b = scan.nextInt();
int c = scan.nextInt();
int d = scan.nextInt();
pair1[i] = new Pair(s,a);
pair2[i] = new Pair(s,b);
pair3[i] = new Pair(s,c);
pair4[i] = new Pair(s,d);
pair5[i] = new Pair(s,a + b + c + d);
}
print(pair1);
print(pair2);
print(pair3);
print(pair4);
print(pair5);
}
}
class Pair implements Comparable<Pair>
{
String name;
int sum ;
Pair(String name ,int sum)
{
this.name = name;
this.sum = sum;
}
@Override
public int compareTo(Pair o) {
// TODO 自动生成的方法存根
return sum == o.sum ? o.name.compareTo(name): Integer.compare(sum, o.sum);
}
}
3、抢气球
算法分析
1、每个小朋友有一个跳的高度，跳的低的小朋友先摘，跳的高的小朋友后摘，2、用结构体存储每个小朋友跳的高度val和编号id，将高度从小到大排序
3、高度从小到大枚举，再枚举所有气球，若未摘且高度允许，则摘并且进行记录，并记录该小朋友摘了多少个气球
时间复杂度 )
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int N = 1010;
static int n,m;
static int[] a = new int[N];
static int[] h = new int[N];
static Pair[] pair = new Pair[N];
static int[] ans = new int[N];//表示某个编号的小朋友能拿到多少个气球
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
a[i] = scan.nextInt();
pair[i] = new Pair(a[i],i);
}
for(int i = 1;i <= m;i ++) h[i] = scan.nextInt();
Arrays.sort(pair,1,n + 1);
for(int i = 1;i <= n;i ++)
{
int val = pair[i].val;
int id = pair[i].id;
int cnt = 0;
for(int j = 1;j <= m;j ++)
{
if(h[j] != -1 && h[j] <= val)
{
h[j] = -1;// 标记已经拿过
cnt ++;
}
}
ans[id] = cnt;
}
for(int i = 1;i <= n;i ++) System.out.println(ans[i]);
}
}
class Pair implements Comparable<Pair>
{
int val,id;
Pair(int val , int id)
{
this.val = val;
this.id = id;
}
@Override
public int compareTo(Pair o) {
// TODO 自动生成的方法存根
return Integer.compare(val, o.val);
}
}
4、抢气球(数据加强版)
算法分析
优化思想：将枚举过的气球不需要重复枚举
在上一题抢气球分析基础下，将气球的高度也从小到大排序，t表示当前枚举到的气球的位置，因此不需要枚举所有气球，只枚举没枚举过的气球，因此遍历所有小朋友和气球的时间复杂度是
时间复杂度 )
Java 代码
import java.util.Scanner;
import java.util.Arrays;
public class Main{
static int N = 100010;
static int n,m;
static int[] a = new int[N];
static int[] h = new int[N];
static Pair[] pair = new Pair[N];
static int[] ans = new int[N];//表示某个编号的小朋友能拿到多少个气球
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
a[i] = scan.nextInt();
pair[i] = new Pair(a[i],i);
}
for(int i = 1;i <= m;i ++) h[i] = scan.nextInt();
Arrays.sort(pair,1,n + 1);
Arrays.sort(h,1,m + 1);
for(int i = 1,t = 1;i <= n;i ++)
{
int val = pair[i].val;
int id = pair[i].id;
int cnt = 0;
while(t <= m && h[t] <= val)
{
cnt ++;
t ++;
}
ans[id] = cnt;
}
for(int i = 1;i <= n;i ++) System.out.println(ans[i]);
}
}
class Pair implements Comparable<Pair>
{
int val,id;
Pair(int val , int id)
{
this.val = val;
this.id = id;
}
@Override
public int compareTo(Pair o) {
// TODO 自动生成的方法存根
return Integer.compare(val, o.val);
}
}
