第4章 结构体

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);
    }
}