@[toc]

前言

前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是300+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！

• 目前是打算参加Java组，所以所有的题解都是Java。

本章节模拟、枚举与排序的习题一览：包含所有题目的Java题解链接

例题：

• AcWing 1210. 枚举-例题 连号区间数 Java题解 （暴力枚举优化）
• AcWing 1236. 枚举-习题 递增三元组 Java题解（排序+二分、排序+双指针、前缀和）
• AcWing 1245. 枚举-例题 特别数的和 Java题解（暴力枚举）
• AcWing 1204. 模拟-例题 错误票据 Java题解（排序、哈希）
• AcWing 466. 枚举-习题 回文日期 Java题解
• AcWing 787. 排序-归并排序 Java题解

习题：

• AcWing 1219. 模拟-习题 移动距离(蓝桥杯) Java题解
• AcWing 1229. 模拟枚举-习题 日期问题 Java题解（模拟、枚举）
• AcWing 1231. 模拟-习题 航班时间(蓝桥杯) Java题解
• AcWing 1241. 模拟-习题 外卖店优先级（蓝桥杯） Java题解
• AcWing 788. 排序-归并排序-习题 逆序对的数量（简单，蓝桥杯）

一、模拟

知识点

枚举与模拟是无算法可言的，只要把题目意思搞懂，按照说的意思去模拟即可。

例题

例题1、AcWing 1245.特别的数的和【简单，蓝桥杯】

题目链接：1245. 特别数的和

分析：

数据范围1≤n≤10000，check所有位数，运行次数大概在6万左右，暴力也肯定是能够AC的。

题解：暴力枚举

复杂度分析：时间复杂度O(n)；空间复杂度O(1)

//10000 * 5，直接暴力模拟

import java.util.*;
import java.io.*;

class Main {
    
    static int n;
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        int res = 0;
        while (n != 0) {
            int sum = n;
            while (sum != 0) {
                int mod = sum % 10;
                if (mod == 2 || mod == 0 || mod == 1 || mod == 9) {
                    res += n;
                    break;
                }
                sum /= 10;
            }
            n--;
        }
        System.out.println(res);
    }
}

---

例题2：AcWing 1204.错误票据【简单，蓝桥杯】

题目链接：1204. 错误票据

分析：

题意：一组打乱的数据（排序后是连续的），找出其中的断号以及重号。

两种方案：

1. 先排序，然后进行遍历一遍。
2. 将所有的数据进行哈希存储，然后去遍历哈希。

思路：

思路1：排序+遍历

复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 10010;
    static int n;
    static int[] arr = new int[N];
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        int pos = 0;
        while (n != 0) {
            String[] s = cin.readLine().split(" ");
            for (int i = 0; i < s.length; i++) {
                arr[pos++] = Integer.valueOf(s[i]); 
            }
            n--;
        }
        //数据一共有pos个
        //排序
        Arrays.sort(arr, 0, pos);
        //遍历
        //m段号、n重号
        int m = 0, n = 0;
        for (int i = 1; i < pos; i++) {
            if (arr[i] == arr[i - 1]) n = arr[i - 1];
            else if (arr[i] == arr[i - 1] + 2) m = arr[i] - 1;
        }
        System.out.printf("%d %d", m, n);
    }
}

思路2：哈希+遍历

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 10010, M = 100010;
    static int count;
    static int[] arr = new int[N];
    //哈希表
    static int[] buckets = new int[M];
    
    public static void main(String[] args)throws Exception {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        count = Integer.valueOf(cin.readLine());
        int pos = 0;
        //结果集的两个变量
        int m = 0, n = 0;
        while (count != 0) {
            String[] s = cin.readLine().split(" ");
            for (int i = 0; i < s.length; i++) {
                arr[pos] = Integer.valueOf(s[i]); 
                buckets[arr[pos]]++;
                //记录重号
                if(buckets[arr[pos]] > 1) {
                    n = arr[pos];
                }
                pos++;
            }
            count--;
        }
        //遍历确定断号
        int minPos = -1;
        for (int i = 0; i < M; i++) {
            if (buckets[i] != 0) {
                minPos = i;
                break;
            }
        }
        for (int i = minPos + 1; i < M; i++) {
            if (buckets[i] == 0) { //若是碰到第一个为空的，那么就是断号
                m = i;
                break;
            }
        }
        System.out.printf("%d %d", m, n);
    }
}

---

例题3、AcWing 466.回文日期【简单】

题目链接：466. 回文日期

分析：

思路1：枚举指定范围中的所有数字，进行check判断。8位数有一千万个数字，那么最少也要O(n)。

• 需要枚举8位数字。

思路2：枚举所有的回文数（4位数），接着去判断是否日期统计个数。（建议）

平年：非闰年都是平年，28天
闰年：年份不能被100整除，能被4整除  ||  能被400整除，29天

解题：

思路1：枚举所有指定范围的回文数（4位数），接着去判断是否日期统计个数。

复杂度分析：时间复杂度O(n)；空间复杂度O(1)。四位数的时间再加上check判断也就几万次，完全能过。

import java.util.*;
import java.io.*;

class Main {
    
    static int begin, end;
    static int[] months = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    public static boolean check(int d) {
        int year = d / 10000;
        int month = d % 10000 / 100;
        int day = d % 100;
        if (month > 12 || month == 0 || day > 31 || day == 0) return false;
        //闰年判断
        if (month != 2 && day > months[month]) return false;
        if (month == 2) {
            int leap = year % 4 == 0 && year % 100 != 0 ? 1 : 0;
            if (day > 28 + leap) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        begin = cin.nextInt();
        end = cin.nextInt();
        int res = 0;
        for (int i = begin / 10000; i <= end / 10000; i++) {
            int day = i, temp = i;
            while (temp != 0) {
                day = day * 10 + temp % 10;
                temp /= 10;
            }
            //避免20101010 => 20100120
            if (day >= begin && day <= end && check(day)) res++;
        }
        System.out.printf("%d", res);
    }
    
}

---

习题

习题1：AcWing 1219.移动距离【简单，蓝桥杯】

来自：第六届蓝桥杯省赛C++B组,第六届蓝桥杯省赛JAVAA/C组

题目链接：1219. 移动距离

分析：

一般距离包含：曼哈顿距离以及欧几里得距离。

题目是要求使用曼哈顿距离来计算。

数字从1234开始都是根据图示的顺序来进行从左至右、从右至左。

w = 每行长度  m = 初始值   n = 结束值

根据案例题目来进行分析：6 8 2
1   2  3  4 5 6
12 11 10  9 8 7
13 12 11 10

实际上他们的距离只需要求到各自数的x,y坐标，然后进行相减绝对值最后相加即可！

例如找12、10它们之间的距离：|3-2| + |4-1| = 4

• 12（2，1）
• 10（3，4）

**题解：**模拟

思路1：模拟，初始位置从1开始，行号也是从1开始。

复杂度分析：时间复杂度O(1)；空间复杂度O(1)

import java.util.*;
import java.io.*;

class Main {
    
    static int w, m, n;
    
    public static int[] getPos(int num) {
        int x = num / w + (num % w == 0 ? 0 : 1);//主要原因就是对于6,12这类数字若是直接/6结果就是2，同一行非整除的就会少一个
        int y = 0;
        //y轴计算：根据规律，奇数是从左到右，偶数时从右到左
        if ((x & 1) == 0) {
            y = w - (num - w * (x - 1)) + 1;//从右往左，想要知道第几个顺序就需要反过来用该行总数来求得是第几个位置
        }else {
            y = num - w * (x - 1);
        }
        return new int[]{x, y};
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        w = cin.nextInt();
        m = cin.nextInt();
        n = cin.nextInt();
        int[] pos1 = getPos(m);
        // System.out.println(Arrays.toString(pos1));
        int[] pos2 = getPos(n);
        // System.out.println(Arrays.toString(pos2));
        System.out.printf("%d", Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]));
    }
}

思路2：模拟，初始位置由0开始，行号也是从0开始。

复杂度分析：时间复杂度O(1)；空间复杂度O(1)。

import java.util.*;
import java.io.*;

class Main {
    
    static int w, m, n;
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        w = cin.nextInt();
        m = cin.nextInt() - 1;
        n = cin.nextInt() - 1;
        int x1 = m / w, x2 = n / w;
        int y1 = m % w, y2 = n % w;
        //若是奇数情况，倒过来求位置
        if ((x1 & 1) == 1) y1 = w - 1 - y1;
        if ((x2 & 1) == 1) y2 = w - 1 - y2;
        System.out.printf("%d", Math.abs(x1 - x2) + Math.abs(y1 - y2));
    }
}

---

习题2：AcWing 1231. 航班时间【简单，蓝桥杯】

来自：第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组

题目链接：1231. 航班时间

• 学习博客：AcWing 1231. 航班时间(java版) 、AcWing 1231. 航班时间

分析：

题目给出中国-中东的往返时间，两地有时差，需要让我们计算出每次飞机往返的时间。【往返时间都是一致的】

两地的往返时间计算，其中time是时差
中国->中东  end1 - start1 + time
中东->中国  end2 - start2 - time
合并一下：(A + B) / 2   =>  (end1 - start1 + time + end2 - start2 - time) / 2  => 
(end1 - start1 + end2 + start2) / 2

其中的难点在于字符串的处理，其他在程序中需要注意的：

①时间的计算，计算总的秒数(距离00:00:00)，之后来进行统一计算。

②输入形式统一，并不是拆分为两种情况，而是没有+1的按照+0来进行处理。

题解：模拟

import java.util.*;
import java.io.*;

class Main {
    
    static int n;
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    
    //获取到h小时m分钟s秒的总共秒数
    public static int get_seconds(int h, int m, int s) {
        return h * 3600 + m * 60 + s;
    } 
    
    public static int get_time()throws Exception {
        String line = cin.readLine();
        //17:21:07 00:31:46 (+1)  => ["17:21:07", "00:31:46", "(+1)"]
        String[] segments = line.split(" ");
        int d = 0;
        //处理隔天的天数
        if (segments.length == 3) d = segments[2].charAt(2) - '0';
        //拆分第一组："17:21:07" => ["17", "21", "07"]
        String[] times = segments[0].split(":");
        int h1 = Integer.valueOf(times[0]), m1 = Integer.valueOf(times[1]), s1 = Integer.valueOf(times[2]);
        //拆分第二组：同上
        times = segments[1].split(":");
        int h2 = Integer.valueOf(times[0]), m2 = Integer.valueOf(times[1]), s2 = Integer.valueOf(times[2]);
        //当天的秒数相减 + d天的完整秒数
        return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
    }
    
    public static void main(String[] args)throws Exception{
        n = Integer.valueOf(cin.readLine());
        while (n-- != 0) {
            //time就是最后每次航程的行驶时间
            int time = (get_time() + get_time()) / 2;
            int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
            System.out.printf("%02d:%02d:%02d\n", hour, minute, second);
        }
    }
}

习题3：AcWing 1241. 外卖店优先级【简单，蓝桥杯】

题目链接：1241. 外卖店优先级

分析：

思路1：暴力解法？是否需要去模拟1 - T时间每一秒的流逝 （在每一秒中去遍历所有的订单，来对相应的店来进行处理） 此时时间复杂度为O(n^2^)

思路2：排序所有的订单，去遍历每个订单的时候，我们需要得知该店铺上一次有订单的时间点，不仅仅要计算+2，还要去处理两个时间点流逝减去的时间。此时复杂度可以优化为O(n.logn)，刚好达到题目要求。

题解：

复杂度：时间复杂度O(n.logn)；空间复杂度O(n)

//题目要求：在第T时刻，有多少家店是在优先缓存当中。
//O(nlogn)
//思路：外卖店 arr[N]
//疑问（暴力解法）？是否需要去模拟1 - T时间每一秒的流逝 （在每一秒中去遍历所有的订单，来对相应的店来进行处理） 此时时间复杂度为O(n^2^)，
//也就是100000 00000  100亿时间，肯定会超时

//排序所有的订单，去遍历每个订单的时候，我们需要得知该店铺上一次有订单的时间点，不仅仅要计算+2，还要去处理两个时间点流逝减去的时间
import java.util.*;
import java.io.*;

class Main {
    static final int N = 100010;
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int n, m, t;
    //对应外卖店的分数表(索引是ID，值为分数)，last时刻表（索引是ID，值是上次的时刻）
    static int[] score = new int[N], last = new int[N];
    //状态表是否已经>=5：（索引是ID，值表示最后t时刻在优先缓存）
    static boolean[] st = new boolean[N];
    //所有的订单表
    static Node[] orders = new Node[N];

    static class Node implements Comparable<Node> {
        public int ts;
        public int id;
        public Node(Integer ts, Integer id) {
            this.ts = ts;
            this.id = id;
        }

        public boolean equals(Node node) {
            return this.ts == node.ts && this.id == node.id;
        }

        @Override
        public int compareTo(Node o) {
            if (this.ts == o.ts) return this.id - o.id;
            return this.ts - o.ts;
        }
    }

    public static void main (String[] args) throws Exception{
        String[] s = cin.readLine().split(" ");
        n = Integer.valueOf(s[0]);
        m = Integer.valueOf(s[1]);
        t = Integer.valueOf(s[2]);

        for (int i = 0; i < m; i++) {
            s = cin.readLine().split(" ");
            orders[i] = new Node(Integer.valueOf(s[0]), Integer.valueOf(s[1]));
        }

        //排序（根据）
        Arrays.sort(orders, 0, m);

        //遍历订单表
        for (int i = 0; i < m; i++) {
            int j = i;
            //比较时刻与id是否都相同
            while (j < m && orders[j].equals(orders[i])) j++;
            //1 1    1  1
            int ts = orders[i].ts;//当前店的时刻
            int id = orders[i].id;//当前店的id
            int cnt = j - i;//有多少个相同时刻的同一家店订单
            //跳过中间连续的一段
            i = j - 1;
            //首先减去之前时刻的时间
            score[id] -= ts - last[id] - 1;
            //若是减去之前时刻<0，那么直接初始化为0
            if (score[id] < 0) score[id] = 0;
            //减去之前的之后来判断是否需要移除
            if (score[id] <= 3) st[id] = false;
            //加上当前的权重（cnt + *2的权重）
            score[id] += cnt * 2;
            //检查当前时刻表是否>5,并加入到优先缓存中，<=3移除
            if (score[id] > 5) st[id] = true;
            //存储下当前店的时刻（方便下一次直接取出指定店家的订单活跃时刻）
            last[id] = ts;
        }
        //遍历所有店家
        int ans = 0;
        for (int id = 1; id <= n; id++) {
            //若是该店家最近的订单活跃时刻不满足t，那么就需要进行减去相应的时刻分数
            if (last[id] < t) {
                score[id] -= t - last[id];
                if (score[id] <= 3) st[id] = false;
            }
            if (st[id]) ans++;
        }
        System.out.printf("%d", ans);
    }
}

---

---

二、枚举

知识点

对于枚举与模拟与求一些算法最优解并不太相同，只需要按照题目的要求能够模拟出来即可，难点在模拟有许多的细节。

例题

例题1：AcWing 1210.连号区间数【简单，蓝桥杯】

题目链接：1210. 连号区间数

分析：

连号区间定义：如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。

例如：3 2 4 1
在[2,3]区间，2与4来进行排序后，并不是递增的，所以该区间并不是连号区间！

暴力思路：O(n^3^.logn)，伪代码如下：O(n^2^.(n.logn + n)) => O(n^3^.logn)，N的最大值为10000，直接超时

for (int l = 0; l < n; l++)  //左括号
	for (int r = l; r < n; r++) { //右括号
		sort(arr,l, r);//对区间进行排序
		boolean flag = true;
        //遍历区间，来检测是否是递增的
		for (int i = l + 1; i < r; i++) {
			if (arr[i] != arr[i - 1] + 1) {
				flag = false;
				break;
			}
		}
		if (flag) res++;
	}

进行思考是否有优化的思路空间？隐藏条件：整个数组中没有相同的数字的，也就是在某个区间中是不会有重复值的，我们只要找到最大值与最小值，令其相减看是否是两个下标相减的值即可判断。

• 连号区间 => max - min = b - a

其中最大值、最小值在进行范围推举的过程中进行计算，这样就可以在O(n^2^)时间复杂度中AC。

题解：在进行区间范围枚举时进行最大值、最小值的推算

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(1)

// 4
// 3 2 4 1

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 10010;
    static int n;
    static int[] arr = new int[N];
    
    public static void main(String[] args) throws Exception {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        for (int i = 0; i < n; i++) arr[i] = cin.nextInt();
        //区间范围遍历（求取区间中最大值、最小值是在进行遍历的过程中进行的）
        int res = 0;//10000 0000 不会超过int最大范围
        for (int l = 0; l < n; l++) {  //左
            int max = -1, min = 10010;
            for (int r = l; r < n; r++) { //右
                //区间范围：[l, r]
                max = Math.max(max, arr[r]);
                min = Math.min(min, arr[r]);
                if (max - min == r - l) res++;
            }
        }
        System.out.printf("%d", res);
    }
}

---

例题2：AcWing 1236.递增三元组【中等，蓝桥杯】

题目链接：1236. 递增三元组

学习文章：AcWing 1236. 递增三元组 (二分+双指针+前缀和)

分析：

先了解题意：根据输入的三组数组中找到满足条件的(i,j,k)三元组方案数。其中条件就是i < j < k

3
1 1 1  i数组
2 2 2  j数组
3 3 3  k数组

对于j数组第一位2，i数组中有3个小于其，k数组有3个小于，那么方案数为3x3
又由于j第二位、第三位同理也是，那么就是3x3x3=27种方案数

首先上来看下暴力是否能够进行解决，O(n^3^)，N的范围是10万，不用想直接超时。

符合N范围的算法一般就是O(n.logn)或者O(n)。该题本质实际上就是去遍历一遍j数组，然后去找<j元素的i数组元素数量，>j元素的k数组元素数量，将其进行相乘即可，重点需要在遍历j数组的过程种来进行优化。

O(n.logn)解可以使用排序+二分、排序+双指针。

• 排序+二分：就是将三组数据排好序之后，接着以B数组种的元素作为基准点，通过二分去找到定位下标。
• 排序+双指针：就是将三组数据排好序之后，接着以B数组种的元素作为基准点，在遍历B数组外定义两个指针，在遍历B元素的每一个元素时，这两个指针不会做重复判断基准位置操作。

O(n)解可以使用前缀和。

• 定义对应a数组、c数组的哈希表，接着对计数哈希表来进行前缀和，之后在遍历b数组的过程中，通过前缀和O(1)的时间复杂度来快速计算得到相应的方案数。

题解：

思路1：前缀和

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {
    static final int N = 100010;
    static int n;
    static int[] a = new int[N], b = new int[N], c = new int[N];
    //存储该数字的出现次数
    static int[] cntsA = new int[N], cntsC = new int[N];
    //对应A，C前缀和
    static int[] sA = new int[N], sC = new int[N];

    public static void main(String[] args) throws Exception{
        //读入数据
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        String[] s = cin.readLine().split(" ");
        //a数组
        for (int i = 0; i < n; i++) {
            a[i] = Integer.valueOf(s[i]);
            //避免值为0的情况
            cntsA[a[i] + 1]++;
        }
        s = cin.readLine().split(" ");
        //b数组
        for (int i = 0; i < n; i++) {
            b[i] = Integer.valueOf(s[i]);
        }
        s = cin.readLine().split(" ");
        //c数组
        for (int i = 0; i < n; i++) {
            c[i] = Integer.valueOf(s[i]);
            cntsC[c[i] + 1]++;
        }
        sA[0] = cntsA[0];
        sC[0] = cntsC[0];
        //计算前缀和
        for (int i = 1; i < N; i++) {
            sA[i] = sA[i - 1] + cntsA[i];
            sC[i] = sC[i - 1] + cntsC[i];
        }

        //遍历b数组
        long res = 0;
        for (int i = 0; i < n; i++) {
            int num = b[i];
            res += (long)(sA[num] * (long)(sC[N - 1] - sC[num + 1]));
        }
        System.out.println(res);
    }
}

思路2：sort + 二分

复杂度分析：时间复杂度O(nlogn)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 100010;
    static int n;
    static int[][] arr = new int[3][N];

    public static void main(String[] args) throws Exception{
        //读入数据
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        for (int i = 0; i < 3; i++) {
            String[] s = cin.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.valueOf(s[j - 1]);
            }
        }
        //排序
        Arrays.sort(arr[0], 1, n + 1);
        Arrays.sort(arr[2], 1, n + 1);
        long ans = 0;
        //以B数组的所有数据作为基准
        for (int i = 1; i <= n; i++) {
            int target = arr[1][i];
            //a数组
            int l = 1, r = n;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (arr[0][mid] >= target) r = mid - 1;
                else l = mid;
            }
            //不符合条件设置为0
            if (arr[0][l] >= target) l = 0;
            int a = l;
            //c数组
            l = 1;
            r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (arr[2][mid] > target) r = mid;
                else l = mid + 1;
            }
            //不符合条件设置为n
            if (arr[2][l] <= target) r = n + 1;
            int c = r;
            //统计数量
            ans += (long)(a * (long)(n - c + 1));
        }
        System.out.println(ans);
    }
}

思路3：sort + 双指针

复杂度分析：时间复杂度O(nlogn)；空间复杂度O(n)

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 100010;
    static int n;
    static int[][] arr = new int[3][N];

    public static void main(String[] args) throws Exception{
        //读入数据
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(cin.readLine());
        for (int i = 0; i < 3; i++) {
            String[] s = cin.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.valueOf(s[j]);
            }
        }
        //排序
        Arrays.sort(arr[0], 0, n);
        Arrays.sort(arr[1], 0, n);
        Arrays.sort(arr[2], 0, n);
        long ans = 0;
        int a = 0, c = 0;
        //以B数组的所有数据作为基准
        for (int i = 0; i < n; i++) {
            int target = arr[1][i];
            while (a < n && arr[0][a] < target) a++;
            while (c < n && target >= arr[2][c]) c++;
            //其中n - c一定要添加long来进行转换，否则就会当成int类型来计算
            ans += (long)(a * (long)(n - c));
        }
        System.out.println(ans);
    }
}

习题

习题1：AcWing 1229.日期问题【枚举、模拟，简单，蓝桥杯】

来自：第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组

题目链接：1229. 日期问题

分析：

思路1：采用枚举思路，将1960年1月1日至2059年12月31日的所有枚举一遍，先进行check是否满足，再进行判断是否是合法的三个数字。（确保了顺序）

• 枚举的数量也就是100万个再加上check时间不会超时。

思路2：直接根据题目给定的日期字符串，然后举出三个并进行排序。（这个思路的话就比较复杂难搞，主要是字符串）

题解：

思路1：枚举

复杂度分析：时间复杂度O(n)；空间复杂度O(1)

import java.util.*;
import java.io.*;

class Main {
    
    static int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    public static boolean check(int year, int month, int day) {
        if (month == 0 || month > 12 || day == 0 || day > 31) return false;
        if (month != 2) {
            if (day > days[month]) return false;
        }else {
            int leap = year % 100 != 0 && year % 4 == 0 || year % 400 == 0 ? 1 : 0;
            if (day > 28 + leap) return false;
        }
        return true;
    }
    
    //枚举19600101 20591231
    //【年/月/日】、【月/日/年】、【日/月/年】
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String[] arr = cin.next().split("/");
        //System.out.println(Arrays.toString(arr));
        int a = (arr[0].charAt(0) - '0') * 10 + arr[0].charAt(1) - '0';
        int b = (arr[1].charAt(0) - '0') * 10 + arr[1].charAt(1) - '0';
        int c = (arr[2].charAt(0) - '0') * 10 + arr[2].charAt(1) - '0';
        //System.out.printf("%d, %d, %d\n",a, b, c);
        for (int i = 19600101; i <= 20591231; i++) {
            int year = i / 10000;
            int month = i % 10000 / 100;
            int day = i % 100;
            if (check(year, month, day)) {
                //若是符合一条就进行输出
                if (year % 100 == a && month == b && day == c || 
                    month == a && day == b && year % 100 == c ||
                    day == a && month == b && year % 100 == c
                ) {
                    System.out.printf("%d-%02d-%02d\n", year, month, day);
                }
            }
        }
    }
    
}

思路2：模拟。

这类模拟是真的比较麻烦，还需要对日期进行排序，这里就直接使用TreeSet来进行排序

复杂度分析：时间复杂度O(1)；空间复杂度O(1)

import java.util.*;
import java.io.*;

class Main {
    
    static int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    public static boolean check(int year, int month, int day) {
        if (month == 0 || month > 12 || day == 0 || day > 31) return false;
        if (month != 2) {
            if (day > days[month]) return false;
        }else {
            int leap = year % 100 != 0 && year % 4 == 0 || year % 400 == 0 ? 1 : 0;
            if (day > 28 + leap) return false;
        }
        return true;
    }
    
    //枚举19600101 20591231
    //【年/月/日】、【月/日/年】、【日/月/年】
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String[] s = cin.next().split("/");
        int a = Integer.valueOf(s[0]);
        int b = Integer.valueOf(s[1]);
        int c = Integer.valueOf(s[2]);
        String s1 = "";
        String s2 = "";
        String s3 = "";
        if (a < 60) s1 = "20" + s[0] + "-" + s[1] + "-" + s[2];
        else s1 = "19" + s[0] + "-" + s[1] + "-" + s[2];
        if (c < 60) {
            s2 = "20" + s[2] + "-" + s[0] + "-" + s[1];
            s3 = "20" + s[2] + "-" + s[1] + "-" + s[0];
        }else {
            s2 = "19" + s[2] + "-" + s[0] + "-" + s[1];
            s3 = "19" + s[2] + "-" + s[1] + "-" + s[0];
        }
        //借助TreeSet排序（对一堆字符串来进行排序，与int类型一致）
        Set<String> set = new TreeSet<>();
        set.add(s1);
        set.add(s2);
        set.add(s3);
        //判断对应的字符串是否符合条件
        boolean f1 = false, f2 = false, f3 = false;
        if (check(a, b, c)) f1 = true;
        if (check(c, a, b)) f2 = true;
        if (check(c, b, a)) f3 = true;
        //遍历set集合
        for (String date: set) {
            if (date.equals(s1) && f1) System.out.println(date);
            else if (date.equals(s2) && f2) System.out.println(date);
            else if (date.equals(s3) && f3) System.out.println(date);
        }
        
    }
    
}

三、排序

例题

例题1：归并排序

题目描述：

时/空限制：1s / 64MB
题目描述：
给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围
1≤n≤100000

输入样例
5
3 1 2 4 5

输出样例
1 2 3 4 5

分析：分而治之。

题解：

import java.util.*;
import java.io.*;

class Main {
    
    static final int N = 100010;
    static int n;
    static int[] arr = new int[N];
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        for (int i = 0; i < n; i++) {
            arr[i] = cin.nextInt();
        }
        //开始进行排序
        mergeSort(arr, 0, arr.length - 1);
        
        for (int i = 0; i < n; i++) {
            System.out.printf("%d ", arr[i]);
        }
    }
    
    public static void mergeSort(int[] arr, int left, int right) {
		if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public static void merge(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int[] temp = new int[right - left + 1];
        int t = 0;
        while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) temp[t++] = arr[i++];
        while (j <= right) temp[t++] = arr[j++];
        System.arraycopy(temp, 0, arr, left, right - left + 1);
    }
    
}