有编号 1 到 n 的 n 个箱子，i 号箱子的重量是 w_i。 名次表有 n 格，每格指向一个箱子。 一开始第 r 格指向 r 号箱子。 命令有五种。 - sort：重新排名次表。 指向较重箱子的格排在前面；重量相同时，编号小的箱子排在前面。 - add r v：给名次表第 r 格所指箱子的重量加上 v。 名次表不重新排。 - swap i j：交换 i 号箱子和 j 号箱子的重量。 名次表的各格仍然指向原来编号的箱子。 i 和 j 可能相同，这时什么也不变。 - who r：在一行中输出名次表第 r 格所指箱子的编号。 - show：从名次表第一格开始依次输出各格所指箱子的 n 个重量，用一个空格隔开，占一行。 第一行给出 n 和 q，第二行给出 w_1 到 w_n，接下来 q 行每行一条命令。 试着把重量放在数组 int w[n] 里，名次表做成指向这些元素的指针数组 int *rank[n]。 sort 时不要搬动重量，只用 qsort（C++ 用 std::sort）排列指针。 重量相同时比较两个指针本身，who 用指针相减 rank[r - 1] - w 求出编号。 swap 写成接收两个元素地址的函数 void swap_weight(int *a, int *b)。
输入
1 ≤ n ≤ 1,000，1 ≤ q ≤ 2,000，1 ≤ r, i, j ≤ n。 重量和 v 都是整数；开始时以及每次 add 之后，所有重量都在 -2,000,000,000 到 2,000,000,000 之间（|v| 也在此范围内）。 所有 show 合计输出的数不超过 15,000 个。 who 或 show 至少出现一次。
输出
每个 who 和 show 一行
样例 1 · stdin
4 10
5 -2 5 7
sort
show
who 2
add 4 10
swap 1 2
show
sort
show
who 3
swap 3 3
stdout
7 5 5 -2
1
7 8 5 5
8 7 5 5
2
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 2 种语言题解
本题只接受 C 和 C++。 把地址当作值来存的指针、指针相减求相隔几格、比较地址大小，只有这两种语言有。 在 Python、JavaScript、TypeScript、Java、C#、Craykon 中，同样的事是在名次表里存箱子编号（下标），再用 w[rank[r]] 找过去（C# 真正的指针只能在 unsafe 中使用）。 C 的 qsort 把待排各格的地址以 const void * 传给比较函数。 格里存的是 int *，所以用 *(int *const *)pa 解一次得到指针，再解一次（*a）才得到重量。 C++ 的 std::sort 直接把两个 const int * 交给比较函数。 指向同一数组内的两个指针可以用 < 比较（地址小，编号也小），相减得到它们之间的格数（rank[r - 1] - w + 1 就是编号）。 五个陷阱：① 比较函数里像 *(const int *)pa 这样只解一次，比较的是指针值的一部分而不是重量，顺序全乱。 ② return *b - *a; 在差超出 int 范围（约 21 亿）时符号会反转，比如 20亿 - (-20亿)。 请比较大小后返回 -1 或 1。 ③ 不用临时变量、写成 *a ^= *b; *b ^= *a; *a ^= *b; 来交换，当 a 和 b 是同一格时（swap 3 3）重量会变成 0。 要时刻记得两个指针可能指向同一处（别名）。 ④ 名次表里不存指针而存重量的副本，add 只改副本，swap 也反映不到名次表上。 ⑤ 重量相同时不按编号区分、交给 C++ 的 std::stable_sort，留下的是经过 add、swap 后当前名次表的顺序，而不是原来的编号顺序。
C++main.cpp · 51 行
#include <algorithm>#include <iostream>#include <string>#include <utility>#include <vector>// a와 b가 같은 칸을 가리켜도 맞게 바꾼다void swap_weight(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<int> w(n); // 상자의 무게. 크기를 다시 바꾸지 않으니 포인터가 계속 맞다 std::vector<int *> rank(n); // 순위표: 칸마다 w의 한 칸을 가리킨다 for (int i = 0; i < n; i++) { std::cin >> w[i]; rank[i] = &w[i]; } for (int k = 0; k < q; k++) { std::string cmd; std::cin >> cmd; if (cmd == "sort") { std::sort(rank.begin(), rank.end(), [](const int *a, const int *b) { if (*a != *b) return *a > *b; return a < b; // 무게가 같으면 주소(= 번호)가 작은 쪽이 앞 }); } else if (cmd == "add") { int r, v; std::cin >> r >> v; *rank[r - 1] += v; } else if (cmd == "swap") { int i, j; std::cin >> i >> j; swap_weight(&w[i - 1], &w[j - 1]); } else if (cmd == "who") { int r; std::cin >> r; std::cout << (rank[r - 1] - w.data()) + 1 << '\n'; } else { for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << *rank[i]; std::cout << '\n'; } } return 0;}
Cmain.c · 53 行
#include <stdio.h>#include <stdlib.h>#include <string.h>static int w[1000]; /* 상자의 무게: w[0]이 1번 상자 */static int *rank[1000]; /* 순위표: 칸마다 w의 한 칸을 가리킨다 *//* qsort는 늘어놓을 칸의 주소를 const void *로 준다. 칸에 든 것이 int *이니 진짜 타입은 int *const * */static int heavier_first(const void *pa, const void *pb) { const int *a = *(int *const *)pa; const int *b = *(int *const *)pb; if (*a != *b) return *a > *b ? -1 : 1; /* 빼기(*b - *a)는 int를 넘칠 수 있다 */ return (a > b) - (a < b); /* 같은 배열 안의 포인터는 크기를 비교할 수 있다: 주소가 작으면 번호도 작다 */}/* a와 b가 같은 칸을 가리켜도 맞게 바꾼다(임시 변수) */static void swap_weight(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp;}int main(void) { int n, q; char cmd[8]; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) { scanf("%d", &w[i]); rank[i] = &w[i]; } for (int k = 0; k < q; k++) { scanf("%7s", cmd); if (strcmp(cmd, "sort") == 0) { qsort(rank, n, sizeof rank[0], heavier_first); } else if (strcmp(cmd, "add") == 0) { int r, v; scanf("%d %d", &r, &v); *rank[r - 1] += v; /* 가리키는 상자의 무게가 바뀐다 */ } else if (strcmp(cmd, "swap") == 0) { int i, j; scanf("%d %d", &i, &j); swap_weight(&w[i - 1], &w[j - 1]); } else if (strcmp(cmd, "who") == 0) { int r; scanf("%d", &r); printf("%d\n", (int)(rank[r - 1] - w) + 1); /* 포인터 빼기 = 몇 칸 떨어져 있나 */ } else { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", *rank[i]); printf("\n"); } } return 0;}