2025寒假算法练习——Week 2
文章目录
习题均来自 NEFU OJ
Problem 1481 | 谁考了第k名-排序
- Description
在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。
- Input
第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。
其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。
- Output
输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩）
- Sample Input
15 3
290788001 67.8
390788002 90.3
490788003 61
590788004 68.4
690788005 73.9
- Sample Output
190788004 68.4
- Source
奥赛一本通
这道题可以自己搓一个排序，也可以用结构体排序解决。
1#include <iostream>
2#include <algorithm>
3
4using namespace std;
5
6struct Student {
7 int id;z
8 float score;
9};
10
11bool cmp(Student a, Student b) {
12 return a.score > b.score;
13}
14
15int main() {
16 Student students[100];
17 int n, k;
18 cin >> n >> k;
19 for (int i = 0; i < n; i++) {
20 cin >> students[i].id >> students[i].score;
21 }
22
23 sort(students, students + n, cmp);
24 printf("%d %g", students[k - 1].id, students[k - 1].score);
25
26 return 0;
27}
AC！
Java 版：
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4import java.text.DecimalFormat;
5
6public class Main {
7 public static void main(String[] args) {
8 Scanner scanner = new Scanner(System.in);
9 int n = scanner.nextInt();
10 int k = scanner.nextInt();
11 List<Student> students = new ArrayList<>();
12 for (int i = 0; i < n; i++) {
13 int id = scanner.nextInt();
14 double score = scanner.nextDouble();
15 students.add(new Student(id, score));
16 }
17 scanner.close();
18 Student result = students.stream()
19 .sorted((a, b) -> Double.compare(b.score, a.score))
20 .skip(k - 1)
21 .findFirst()
22 .get();
23
24 DecimalFormat df = new DecimalFormat("0.###");
25 System.out.println(String.format("%d %s", result.id, df.format(result.score)));
26 }
27}
28
29class Student {
30 public int id;
31 public double score;
32
33 public Student(int id, double score) {
34 this.id = id;
35 this.score = score;
36 }
37}
AC！
不管是 String.format 还是 System.out.printf，使用 %g 来格式化都会默认保留六位小数，所以使用 DecimalFormat 去掉小鼠先后尾随 0。 ### 表示最多显示六位小数，不显示不必要的 0。
Python 版：
1class Student:
2
3 def __init__(self, id, score):
4 self.id = id
5 self.score = score
6
7 def __repr__(self):
8 return f"{self.id} {self.score}"
9
10
11def main():
12 n, k = map(int, input().strip().split(" "))
13 students = list()
14 for _ in range(n):
15 data = input().strip().split(" ")
16 students.append(Student(data[0], float(data[1])))
17
18 students = sorted(students, key=lambda s: s.score)
19 print(students[k - 1])
20
21
22if __name__ == "__main__":
23 main()
Problem 1482 | 奇数单增序列
- Description
给定一个长度为N（不大于500）的正整数序列，请将其中的所有奇数取出，并按升序输出
- Input
共2行：
第1行为 N；
第2行为 N 个正整数，其间用空格间隔。
- Output
增序输出的奇数序列，数据之间以逗号间隔。数据保证至少有一个奇数。
- Sample Input
110
21 3 2 6 5 4 9 8 7 10
- Sample Output
11,3,5,7,9
- Source
奥赛一本通
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4import java.util.stream.Collectors;
5
6public class Main {
7 public static void main(String[] args) {
8 List<Integer> odd = new ArrayList<>();
9 try (Scanner sc = new Scanner(System.in)) {
10 int n = sc.nextInt();
11 while (--n > 0) {
12 int num = sc.nextInt();
13 if (num % 2 == 1) {
14 odd.add(num);
15 }
16 }
17 }
18
19 String result = odd.stream()
20 .sorted()
21 .map(i -> i.toString())
22 .collect(Collectors.joining(","));
23 System.out.println(result);
24
25 }
26}
AC！
Problem 1483 | 成绩排序
- Description
给出班里某门课程的成绩单，请你按成绩从高到低对成绩单排序输出，如果有相同分数则名字字典序小的在前。
- Input
第一行为n (0 < n < 20)，表示班里的学生数目；
接下来的n行，每行为每个学生的名字和他的成绩, 中间用单个空格隔开。名字只包含字母且长度不超过20，成绩为一个不大于100的非负整数。
- Output
把成绩单按分数从高到低的顺序进行排序并输出，每行包含名字和分数两项，之间有一个空格。
- Sample Input
14
2Kitty 80
3Hanmeimei 90
4Joey 92
5Tim 28
- Sample Output
1Joey 92
2Hanmeimei 90
3Kitty 80
4Tim 28
- Source
奥赛一本通
又是一个结构体排序，但是有多个条件。
C++ 版：
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Student {
8 string name;
9 int score;
10};
11
12bool cmp(Student a, Student b) {
13 if (a.score != b.score) {
14 return a.score > b.score;
15 }
16 return a.name < b.name;
17}
18
19int main() {
20 vector<Student> students;
21 int n;
22 cin >> n;
23 while (n--) {
24 string name;
25 int score;
26 cin >> name >> score;
27 students.push_back(Student{ name, score });
28 }
29
30 sort(students.begin(), students.end(), cmp);
31
32 for (const auto& student : students) {
33 printf("%s %d\n", student.name.c_str(), student.score);
34 }
35}
AC！
Java 版：
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4
5public class Main {
6 public static void main(String[] args) {
7 List<Student> students = new ArrayList<>();
8 try (Scanner sc = new Scanner(System.in)) {
9 int n = sc.nextInt();
10 sc.nextLine();
11 while (n-- > 0) {
12 String[] data = sc.nextLine().split("\\s+");
13 String name = data[0];
14 int score = Integer.parseInt(data[1]);
15 students.add(new Student(name, score));
16 }
17 }
18
19 students.sort((a, b) -> {
20 if (a.score != b.score) {
21 return Integer.compare(b.score, a.score);
22 }
23 return a.name.compareTo(b.name);
24 });
25
26 for (Student student : students) {
27 System.out.println(student);
28 }
29
30 }
31}
32
33class Student {
34 public String name;
35 public int score;
36
37 public Student(String name, int score) {
38 this.name = name;
39 this.score = score;
40 }
41
42 @Override
43 public String toString() {
44 return String.format("%s %d", this.name, this.score);
45 }
46}
AC！
上面是使用 sort 方法和 Lambda 表达式的写法。OJ 声称其使用 jdk 1.5.0，但是 Lambda 表达式在 Java 8 中才加入，我提交后依然能过。
下面是使用 Comparator 接口实现排序：
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4import java.util.Comparator;
5
6public class Main {
7 public static void main(String[] args) {
8 List<Student> students = new ArrayList<>();
9 try (Scanner sc = new Scanner(System.in)) {
10 int n = sc.nextInt();
11 sc.nextLine();
12 while (n-- > 0) {
13 String[] data = sc.nextLine().split("\\s+");
14 String name = data[0];
15 int score = Integer.parseInt(data[1]);
16 students.add(new Student(name, score));
17 }
18 }
19
20 students.sort(Comparator.comparing(Student::getScore).reversed().thenComparing(Student::getName));
21
22 for (Student student : students) {
23 System.out.println(student);
24 }
25
26 }
27}
28
29class Student {
30 public String name;
31 public int score;
32
33 public Student(String name, int score) {
34 this.name = name;
35 this.score = score;
36 }
37
38 public String getName() {
39 return this.name;
40 }
41
42 public int getScore() {
43 return this.score;
44 }
45
46 @Override
47 public String toString() {
48 return String.format("%s %d", this.name, this.score);
49 }
50}
AC！
这种写法比直接写 Lambda 表达式稍快一些，内存开销也略小。
这样排序需要实现 Student 对应的方法。如果没有实现方法而要直接访问属性，则还是需要在 Comparator.comparing 中使用 Lambda 表达式：students.sort(Comparator.comparing((Student s) -> s.score).reversed().thenComparing((Student s) -> s.name));。
Python 版：
1class Student:
2
3 def __init__(self, name: str, score: int):
4 self.name = name
5 self.score = score
6
7 def __repr__(self):
8 return f"{self.name} {self.score}"
9
10
11def main():
12 n = int(input())
13 students = list()
14 for _ in range(n):
15 data = input().split(" ")
16 students.append(Student(data[0], int(data[1])))
17
18 students.sort(key=lambda s: (-s.score, s.name))
19 for student in students:
20 print(student)
21
22
23if __name__ == "__main__":
24 main()
Problem 1650 | 没必要的排序2
- Description
羽裳有n个数，她想知道前k大的数的和是多少
- Input
输入n，k代表有n个数，求前k大的和,之后输入n个数，第i个数为a[i]
1<=n<=10000000(1e7)
1<=k<1000
对任意的i
1<=a[i]<=100000(1e5)
- Output
输出一个数ans，ans是前k大数的和
- Sample Input
12 1
299999 1
- Sample Output
199999
- Hint
排序会超时
没有必要排序，只需要找到前 k 大的数据并求和就可以。首先创建一个长度为 k 的数组 a 用于存储最大的 k 个数据。当已经输入的数据数量小于 k 时，直接把数据存进 a；当 k 满了的时候，如果新输入的数据大于 a 的最小值，则用这个数据替换 a 的最小值。当所有数据都输入完后，这个数组里存储的就是最大的 k 个元素。
1// MSVC 特色
2// #define _CRT_SECURE_NO_WARNINGS
3
4#include <cstdio>
5
6int main() {
7 int n, k, p, nums[1005] = { 0 };
8 scanf("%d %d", &n, &k);
9 p = n - k;
10
11 for (int i = 0; i < k; i++) {
12 scanf("%d", &nums[i]);
13 }
14
15 int min_num = 0x3f3f3f3f, min_index = -1;
16 for (int i = 0; i < k; i++) {
17 if (nums[i] < min_num) {
18 min_num = nums[i];
19 min_index = i;
20 }
21 }
22
23 while (p--) {
24 int num;
25 scanf("%d", &num);
26 if (num > min_num) {
27 nums[min_index] = num;
28 min_num = 0x3f3f3f3f;
29 min_index = -1;
30 for (int i = 0; i < k; i++) {
31 if (nums[i] < min_num) {
32 min_num = nums[i];
33 min_index = i;
34 }
35 }
36 }
37 }
38
39 long long int sum = 0;
40 for (int i = 0; i < k; i++) {
41 sum += nums[i];
42 }
43 printf("%lld", sum);
44
45 return 0;
46}
这道题的测试点的数据量太大了，使用 cin 和 cout 时会以 1672k - 3000ms 的战绩超时，而使用 printf 和 scanf 只用 1064k - 1186ms。
这道题也可以使用优先队列解决。因为不需要对元素随机访问，优先队列是比二叉搜索树或者红黑树更好的选择。
1// #define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <queue>
5#include <vector>
6
7using namespace std;
8
9int main() {
10 int n, k;
11 scanf("%d %d", &n, &k);
12
13 priority_queue<int, vector<int>, greater<int>> pq;
14
15 int num;
16 while (n--) {
17 scanf("%d", &num);
18 if (pq.size() < k) {
19 pq.push(num);
20 }
21 else if (num > pq.top()) {
22 pq.pop();
23 pq.push(num);
24 }
25 }
26
27 long long int sum = 0;
28 while (!pq.empty()) {
29 sum += pq.top();
30 pq.pop();
31 }
32 printf("%lld", sum);
33
34 return 0;
35}
同样，使用 cin 和 cout 读写会消耗 1680k - 3000ms，而使用 printf 和 scanf 读写只需要 1232k - 1671ms 就能完美通过。
Problem 554 | 老和尚的导员
- Description
等小和尚回来后，老和尚居然没有睡觉。老和尚表示他的导员的excel表格坏掉了（老和尚居然有导员？好吧……据说是方丈），而且老和尚的导员要老和尚将寺中所有和尚的期末考试成绩按降序排列来发奖学金（和尚还有奖学金？）
不用多说，为了继续睡午觉，这个任务理所当然的落在了小和尚身上。所有……你继续帮忙吧。
- Input
寺中主要考试科目有C语言，线性代数，高等数学和英语四个科目（怎么当和尚都这么累），输入的第一行是和尚的人数N（N<=100），第二行至第N+1行分别为C语言a[i]，线性代数b[i]，高等数学c[i]和英语的成绩d[i](0 <= a[i],b[i],c[i],d[i] <= 100)。
- Output
现需要你将和尚们的成绩以总成绩降序排列，输出数据的每行有两个数字，第一个数字为和尚的编号（输入时的第一个和尚成绩即为和尚1，第二个为和尚2），第二个数字为和尚的总成绩（如果总成绩相同，则按C语言的成绩排列，如在相同，则按线性代数输出编号，以此类推。）
- Sample Input
15
298 50 27 65
358 52 24 16
498 96 90 89
531 65 98 78
665 67 66 90
- Sample Output
13 373
25 288
34 272
41 240
52 150
这题我浪费一下午时间。题本身 ez，但是测试点有多组输入，而题目描述里没说。我看了题解才知道要改成 while (scanf("%d", &n) != EOF) 🤯。
1#include<cstdio>
2#include<algorithm>
3
4using namespace std;
5
6typedef struct Student {
7 int a, b, c, d, sum, num;
8} Student;
9
10Student students[105];
11
12bool cmp(Student x, Student y) {
13 if (x.sum != y.sum) {
14 return x.sum > y.sum;
15 }
16 else if (x.a != y.a) {
17 return x.a > y.a;
18 }
19 else if (x.b != y.b) {
20 return x.b > y.b;
21 }
22 else if (x.c != y.c) {
23 return x.c > y.c;
24 }
25 else {
26 return x.d > y.d;
27 }
28}
29
30int main() {
31 int n;
32 while (scanf("%d", &n) != EOF) {
33 for (int i = 1; i <= n; i++) {
34 students[i].num = i;
35 scanf("%d%d%d%d", &students[i].a, &students[i].b, &students[i].c, &students[i].d);
36 students[i].sum = students[i].a + students[i].b + students[i].c + students[i].d;
37 }
38
39 sort(students + 1, students + n + 1, cmp);
40
41 for (int i = 1; i <= n; i++) {
42 printf("%d %d\n", students[i].num, students[i].sum);
43 }
44 }
45 return 0;
46}
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4import java.util.Comparator;
5
6public class Main {
7 public static void main(String[] args) {
8 Scanner sc = new Scanner(System.in);
9
10 while (sc.hasNextInt()) {
11 int n = sc.nextInt();
12 List<Student> students = new ArrayList<Student>();
13 int C, LM, HM, Eng;
14 for (int i = 1; i <= n; i++) {
15 C = sc.nextInt();
16 LM = sc.nextInt();
17 HM = sc.nextInt();
18 Eng = sc.nextInt();
19 students.add(new Student(C, LM, HM, Eng, i));
20 }
21
22 students.sort(Comparator.<Student, Integer>comparing(Student::getTotal).reversed()
23 .thenComparing(Student::getC)
24 .thenComparing(Student::getLM)
25 .thenComparing(Student::getHM)
26 .thenComparing(Student::getEng));
27
28 for (Student s : students) {
29 System.out.println(s);
30 }
31 }
32
33 sc.close();
34 }
35}
36
37class Student {
38 public int C;
39 public int LM;
40 public int HM;
41 public int Eng;
42 public int total;
43 public int number;
44
45 public Student(int C, int LM, int HM, int Eng, int number) {
46 this.C = 100 - C;
47 this.LM = 100 - LM;
48 this.HM = 100 - HM;
49 this.Eng = 100 - Eng;
50 this.total = C + LM + HM + Eng;
51 this.number = number;
52 }
53
54 public int getTotal() {
55 return this.total;
56 }
57
58 public int getC() {
59 return this.C;
60 }
61
62 public int getLM() {
63 return this.LM;
64 }
65
66 public int getHM() {
67 return this.HM;
68 }
69
70 public int getEng() {
71 return this.Eng;
72 }
73
74 @Override
75 public String toString() {
76 return String.format("%d %d", this.number, this.total);
77 }
78}
Problem 556 | 健忘的老和尚
- Description
当小和尚排完名单后，老和尚突然一拍脑袋：“导员把每个人的人名都给我了，可我忘记告诉你了。”好吧……我们可怜的小和尚看来要费二遍事了（好像之前的任务都是你帮他做的，好吧，你真可怜）
- Input
输入数据为多组，输入的第一行为和尚的人数N，可以得到奖学金的人数M，和需要补考的人数O（在这里可以满足M+O<=N，即得到奖学金的和尚一定不用参加补考）。之后的N行每行都有一个字符串（即为和尚的名字，长度小于100）和尚考试的总分a[i](0 <= a[i] <= 1000)。
- Output
前M行，每行是获得奖学金的小和尚的名字；
后O行，每行是补考的小和尚的名字；
由于老和尚觉得很对不起小和尚，所以他决定这次简单些，所以无论是奖励还是惩罚都按照总成绩从低到高输出和尚的名字即可。
- Sample Input
15 1 2
2a 192
3aa 212
4ab 351
5bab 128
6bbaa 654
- Sample Output
1bbaa
2bab
3a
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4
5public class Main {
6 public static void main(String[] args) {
7 Scanner scanner = new Scanner(System.in);
8 while (scanner.hasNextInt()) {
9 int n = scanner.nextInt();
10 int m = scanner.nextInt();
11 int o = scanner.nextInt();
12 scanner.nextLine();
13
14 List<Student> students = new ArrayList<>();
15 for (int i = 0; i < n; i++) {
16 String[] data = scanner.nextLine().trim().split("\\s+");
17 students.add(new Student(data[0], Integer.parseInt(data[1])));
18 }
19
20 students.sort((a, b) -> Integer.compare(a.score, b.score));
21
22 for (int i = n - m; i < n; i++) {
23 System.out.println(students.get(i));
24 }
25
26 for (int i = 0; i < o; i++) {
27 System.out.println(students.get(i));
28 }
29 }
30 scanner.close();
31 }
32}
33
34class Student {
35 public String name;
36 public int score;
37
38 public Student(String name, int score) {
39 this.name = name;
40 this.score = score;
41 }
42
43 @Override
44 public String toString() {
45 return this.name;
46 }
47}
Problem 873 | 戏说三国
- Description
东汉末年，宦官当权，民不聊生。灵帝中平元年，张角兄弟发动黄巾起义，官军闻风丧胆。为抵抗黄巾，幽州太守刘焉出榜招兵。榜文前，刘备、关羽、张飞三兄弟萍水相逢。三人都有为国效力之心，于是桃园结为异姓兄弟，开始了一段三国浪漫传奇……
如果我问你三国中谁最聪明你一定会说是诸葛亮，我要问你谁武功最高，保不准你就要说关羽。是啊，我们的刘备对于优秀的手下向来十分满意。可是有一天，刘备在无意间在朋友圈里看到了梁山的宋江正在进行英雄排座次，最可气的是这条动态已经被转发评论了无数次了……这一下可气坏了刘备，他决定也来一次，蜀中文武百官大排名。
为了公平起见，诸葛亮帮他制定一条评分标准：每个官员有一个智育、德育、武育三个分数，分别以b%，a%，c%的比率计入加权总分，按总分降序排列，总分相同按智育折合后的分数降序，智育相同按德育，依次类推最终决定排名。（保证没有排名一样的两个人）
- Input
输入第一行t(1<=t<=1000)表示输入的组数。接下来每组第一行1个整数n（1<=n<=100000）三个实数a,b,c(a+b+c=100)接下来n行每行包括英雄的名字，字符串s（1<=len<=20,全为小写字母） 智育、德育、武育的分数（整数）。（1~100）
- Output
每组第一行输出是第几组输出Case #t：接下来输出n行每行包括英雄的名字，总分，智育、德育、武育折合后的分数（保留四位小数）。
- Sample Input
11
23 20.00 20.00 60.00
3zhugeliang 90 80 0
4zhangfei 0 0 100
5guanyu 10 100 100
- Sample Output
1Case #1:
2guanyu 82.0000 2.0000 20.0000 60.0000
3zhangfei 60.0000 0.0000 0.0000 60.0000
4zhugeliang 34.0000 18.0000 16.0000 0.0000
a b c 顺序是反的
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4import java.util.Comparator;
5
6public class Main {
7 public static void main(String[] args) {
8 Scanner scanner = new Scanner(System.in);
9 int t = scanner.nextInt();
10
11 for (int i = 1; i <= t; i++) {
12 int n = scanner.nextInt();
13 double pa = scanner.nextDouble();
14 double pb = scanner.nextDouble();
15 double pc = scanner.nextDouble();
16 scanner.nextLine();
17
18 List<Officer> officers = new ArrayList<>();
19 while (n-- > 0) {
20 String[] data = scanner.nextLine().trim().split("\\s+");
21 double a = Double.parseDouble(data[1]) * pb / 100.0;
22 double b = Double.parseDouble(data[2]) * pa / 100.0;
23 double c = Double.parseDouble(data[3]) * pc / 100.0;
24 officers.add(new Officer(data[0], a, b, c));
25 }
26
27 officers.sort(Comparator.comparing(Officer::getSum)
28 .thenComparing(Officer::getA)
29 .thenComparing(Officer::getB)
30 .thenComparing(Officer::getC));
31
32 System.out.println(String.format("Case #%d:", i));
33 for (Officer officer : officers) {
34 System.out.println(officer);
35 }
36 }
37
38 scanner.close();
39 }
40}
41
42class Officer {
43 public String name;
44 public double a, b, c;
45 public double sum;
46
47 public Officer(String name, double a, double b, double c) {
48 this.name = name;
49 this.a = a;
50 this.b = b;
51 this.c = c;
52 this.sum = a + b + c;
53 }
54
55 @Override
56 public String toString() {
57 return String.format("%s %.4f %.4f %.4f %.4f", name, sum, a, b, c);
58 }
59
60 public double getSum() {
61 return 100.0 - sum;
62 }
63
64 public double getA() {
65 return 100.0 - a;
66 }
67
68 public double getB() {
69 return 100.0 - b;
70 }
71
72 public double getC() {
73 return 100.0 - c;
74 }
75}
Problem 1297 | 结构体排序一
- Description
现在给定一组二维平面上面的点的坐标,保证它的坐标是int类型的整数且大于等于0小于等于99.请你按照数据所给要求进行排序.
首先先以横坐标进行排序,若横坐标相同则按纵坐标排序,降序或升序将以0和1的形式表示,0表示降序,1表示升序.
比如,若数据开头给出0 1的要求,则表示先以横坐标降序排列,若横坐标相同则按纵坐标升序排列.
再比如,若数据开头给出1 1的要求,则表示先以横坐标升序排列,若横坐标相同则按纵坐标升序排列.
保证点的数量大于等于3小于等于99
- Input
第1行包含三个数字,第一个数字和第二个数字分别表示横坐标和纵坐标的排序要求,0表示降序,1表示升序,第三个数字n表示有几个点需要排序.
余下第2~n+1行每行各有两个类型为n个点的坐标,例如第2行第一个数字表示第一个点横坐标,第二个数字表示第一个点的纵坐标.
- Output
输出n行坐标,一行表示一个点,格式如下:
(x0,y0)
- Sample Input
10 0 4
21 1
31 2
42 1
52 2
61 1 4
72 2
82 1
91 2
101 1
- Sample Output
1(2,2)
2(2,1)
3(1,2)
4(1,1)
5(1,1)
6(1,2)
7(2,1)
8(2,2)
1import java.util.Scanner;
2import java.util.List;
3import java.util.ArrayList;
4
5public class Main {
6 public static void main(String[] args) {
7 int a, b, n, x, y, pair;
8 Scanner scanner = new Scanner(System.in);
9 while (scanner.hasNextInt()) {
10 a = scanner.nextInt();
11 b = scanner.nextInt();
12 n = scanner.nextInt();
13
14 pair = decode(a, b);
15 List<Point> points = new ArrayList<>();
16 while (n-- > 0) {
17 x = scanner.nextInt();
18 y = scanner.nextInt();
19 points.add(new Point(x, y));
20 }
21
22 switch (pair) {
23 case 0:
24 points.sort((p, q) -> {
25 if (p.x != q.x) {
26 return Integer.compare(q.x, p.x);
27 }
28 return Integer.compare(q.y, p.y);
29 });
30 break;
31 case 1:
32 points.sort((p, q) -> {
33 if (p.x != q.x) {
34 return Integer.compare(q.x, p.x);
35 }
36 return Integer.compare(p.y, q.y);
37 });
38 break;
39 case 2:
40 points.sort((p, q) -> {
41 if (p.x != q.x) {
42 return Integer.compare(p.x, q.x);
43 }
44 return Integer.compare(q.y, p.y);
45 });
46 break;
47 case 3:
48 points.sort((p, q) -> {
49 if (p.x != q.x) {
50 return Integer.compare(p.x, q.x);
51 }
52 return Integer.compare(p.y, q.y);
53 });
54 break;
55 default:
56 break;
57 }
58
59 for (Point point : points) {
60 System.out.println(point);
61 }
62 }
63 scanner.close();
64 }
65
66 public static int decode(int x, int y) {
67 return x * 2 + y * 1;
68 }
69}
70
71class Point {
72 public int x, y;
73
74 public Point(int x, int y) {
75 this.x = x;
76 this.y = y;
77 }
78
79 @Override
80 public String toString() {
81 return String.format("(%d,%d)", x, y);
82 }
83}
才注意到这道题是结构体排序。
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Point {
8 int x, y;
9};
10
11int decode(int x, int y) {
12 return x * 2 + y;
13}
14
15int main() {
16 int a, b, n, x, y, pair;
17 while (cin >> a >> b >> n) {
18 pair = decode(a, b);
19 vector<Point> points;
20 while (n--) {
21 Point p;
22 cin >> p.x >> p.y;
23 points.push_back(p);
24 }
25
26 switch (pair) {
27 case 0:
28 sort(points.begin(), points.end(), [](Point p, Point q) {
29 if (p.x != q.x) {
30 return p.x > q.x;
31 }
32 return p.y > q.y;
33 });
34 break;
35 case 1:
36 sort(points.begin(), points.end(), [](Point p, Point q) {
37 if (p.x != q.x) {
38 return p.x > q.x;
39 }
40 return p.y < q.y;
41 });
42 break;
43 case 2:
44 sort(points.begin(), points.end(), [](Point p, Point q) {
45 if (p.x != q.x) {
46 return p.x < q.x;
47 }
48 return p.y > q.y;
49 });
50 break;
51 case 3:
52 sort(points.begin(), points.end(), [](Point p, Point q) {
53 if (p.x != q.x) {
54 return p.x < q.x;
55 }
56 return p.y < q.y;
57 });
58 break;
59 default:
60 break;
61 }
62
63 for (const auto& p : points) {
64 printf("(%d,%d)\n", p.x, p.y);
65 }
66 }
67 return 0;
68}
Problem 1298 | 结构体排序二
- Description
给定一些三维空间的点,要求给它们进行排序,其中点的坐标是大于等于0小于等于99的int类型的整数.
排序要求是,首先按横坐标x升序排列,若横坐标x相同则按纵坐标y升序排列,若纵坐标y相同则按竖坐标z升序排列.
保证点的数量大于等于3小于等于99.
- Input
第1行有一个数字n,表示需要排序的点的个数
第2~n+1行各有三个整数,分别表示点的横坐标,纵坐标,竖坐标.
- Output
输出n行,每行表示一个点,格式如下:
(x,y,z)
- Sample Input
15
24 7 9
32 3 1
43 5 6
53 5 9
64 8 7
- Sample Output
1(2,3,1)
2(3,5,6)
3(3,5,9)
4(4,7,9)
5(4,8,7)
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Point {
8 int x, y, z;
9};
10
11bool cmp(Point p, Point q) {
12 if (p.x != q.x) {
13 return p.x < q.x;
14 }
15 else if (p.y != q.y) {
16 return p.y < q.y;
17 }
18 else {
19 return p.z < q.z;
20 }
21}
22
23int main() {
24 int n;
25 while (cin >> n) {
26 vector<Point> points;
27 while (n--) {
28 Point p;
29 cin >> p.x >> p.y >> p.z;
30 points.push_back(p);
31 }
32 sort(points.begin(), points.end(), cmp);
33
34 for (const auto& p : points) {
35 printf("(%d,%d,%d)\n", p.x, p.y, p.z);
36 }
37 }
38 return 0;
39}