牛客-策策学长找py

题目描述

在上一集中(新生赛)，策策学长的 hxd 终于帮助策策学长打到了超凡大师，但是他却拿走了策策学长的 py。（某python项目源码（真的是源码吗？））
策策学长决定找回他自己 py，但他的 py 被分裂成了 k 份，被无情的散布在一个 n×m 的网格中，他需要找回所有的 py 碎片来重获 py。
策策学长从 (1, 1)(1,1) 出发走到 (n, m)(n,m)，每次只能向下或者向右移动一格，策策学长会在移动的过程中收集 py 碎片，请你帮他判断是否能收集到所有的 py 碎片。

输入描述

第一行有一个正整数 T(1<=T<=1000)，表示有 T 组数据。对于每一组样例，第一行有三个正整数 n, m, k，其中 1<=n,m<=10^4,1<=k<=nm.接下来的 k 行，每行有两个正整数xi,yi其中1 <= xi <= n,1 <= yi <= m.保证全部 T 组输入满足∑k⩽2×10 ^5,同一个格子可能含有多个py碎片。

输入描述

输出 TT 行, 每行输出 `YES` 或者 `NO`, 
表示策策学长是否能找回他的 py。

示例 1:

输入：
2
3 3 3
1 1
2 2
3 3
3 3 3
1 1
1 2
2 1
输出：
YES
NO

说明

样例的两张图如下所示：
左图可以通过：向右、向下、向右、向下的步骤找到所有 py 碎片，输出 YES， 右图无解输出 NO.

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;public class Main {//拿人家py真过分public static void main(String[] args) throws IOException {//InputReader是自己写的一个输出类，代码就不放了，你可以换成scanner。InputReader scanner = new InputReader(System.in);int t = scanner.nextInt();for (int i = 0; i < t; i++) {int n = scanner.nextInt();int m  = scanner.nextInt();int k  = scanner.nextInt();int[][] arr = new int[k][2];boolean flag = true;for (int j = 0; j < k; j++) {arr[j][0] = scanner.nextInt();arr[j][1] = scanner.nextInt();}Arrays.sort(arr, new sort2());for (int j = 0; j < k-1; j++) {if(arr[j+1][1] < arr[j][1]){flag = false;break;}}if (flag) {System.out.println("YES");}else {System.out.println("NO");}}}
}
class sort2 implements Comparator<int[]> {@Overridepublic int compare(int[] o1, int[] o2) {if(o1[0] > o2[0]) {return 1;} else if(o1[0] == o2[0]){if(o1[1] > o2[1]){return 1;}else if(o1[1] == o2[1]){return 0;}else{               return -1;}}else{return -1;}}
}

解题思路

对数组进行排序，要自定义排序规则，注意不要写错，比赛时就因为一个下标写错，结果一直没过去（草），
优先对x排序，x想等则对y排序，我们只需保证排序后的数组中y有序递增即可证明可以收集到全部py（笑😂 ），不要想着生成数组后用什么动归，那玩意时间复杂度应该是nmt，太高了，而且生成数组会占用大量空间，我们这样时间复杂度是tlogk，而且空间应该也是tk。