解释：挨个试，对于每一个数x从二开始试，直到根号x
#include<cstdio> using namespace std; int n, m; int a[100], b[100]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) a[i] = b[i] = 0; for (int i = 1; i <= m; ++i) { int x, y; scanf("%d%d", &x, &y); if (a[x] < y && b[y] < x) { if (a[x] > 0) b[a[x]] = 0; if (b[y] > 0) a[b[y]] = 0; a[x] = y; b[y] = x; } } int ans = 0; for (int i = 1; i <= n; ++i) { if (a[i] == 0) ++ans; if (b[i] == 0) ++ans; } printf("%d", ans); return 0; } ```解释：
#include <iostream> using namespace std; const int maxn = 10000; int n; int a[maxn]; int b[maxn]; int f(int l, int r, int depth) { if (l > r) return 0; int min = maxn, mink; for (int i = l; i <= r; ++i) { if (min > a[i]) { min = a[i]; mink = i; } } int lres = f(l, mink - 1, depth + 1); int rres = f(mink + 1, r, depth + 1); return lres + rres + depth * b[mink]; } int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> b[i]; cout << f(0, n - 1, 1) << endl; return 0; } ```解释（1）： f()中返回lres + rres + depth * b[mink]，如果b[]全为0，结果一定为0。 解释（2）： 已知b[0] = 1, b[1] = 2, ..., b[9] = 10，要输出最大值，即depth * b[mink]的和最大，那么depth的值应该尽可能的大。与上道题类似，数组a[]中元素是有序的，才能保证归深度最大，最大值= 1 × 1 + 2 × 2 + 3 × 3 + . . . + 10 × 10 = 385
（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小到大排序。
例如有三对整数（3，4）、（2，4）、（3，3），那么排序之后应该是（2，4）、（3，3）、（3，4）。
输入第一行为 nn，接下来 nn 行，第 ii 行有两个数 a[i] 和 b[i]，分别表示第 ii 对整数的第一关键字和第二关键字。
提示：应先对第二关键字排序，再对第一关键字排序。数组 ord_____ 存储第二关键字排序的结果，数组 res_____ 存储双关键字排序的结果。
试补全程序
#include <cstdio> #include <cstring> using namespace std; const int maxn = 10000000; const int maxs = 10000; int n; unsigned a[maxn], b[maxn],res[maxn], ord[maxn]; unsigned cnt[maxs + 1]; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; ++i) ①; // 利用 cnt 数组统计数量 for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i]; for (int i = 0; i < n; ++i) ②; // 记录初步排序结果 memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; ++i) ③; // 利用 cnt 数组统计数量 for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i]; for (int i = n - 1; i >= 0; --i) ④ // 记录最终排序结果 for (int i = 0; i < n; i++) printf("%d %d", ⑤); return 0; }解释： 计数排序，通过统计每个待排序元素的出现次数，实现排序。本题中，cnt[]数组分别统计了两个关键字数组中每个元素的出现次数，同时又进一步处理了在区间 （0,10000）中，前i个数中小于等于i的关键字个数，可以计算每个关键字的排名。 数组 ord[] 和数组 res[] 都是以排名为下标，记录关键字在数组中的位置。数组 ord[] 存储第二关键字排序的结果，ord[i] = j表示排名为i的第二个关键字在数组b[j]中。数组 res[] 存储双关键字排序的结果，res[i] = j表示最终排名为i的关键字在数组a[j]、b[j]中。 空①，题目中提示先对第二个关键字排序，所以次空应填：cnt[b[i]]++，记录所有第二个关键字的出现次数。 空②，记录初步排序结果。通过上面代码cnt[i + 1] += cnt[i];，cnt[i]存储了小于等于i的第二关键字的个数，那么cnt[b[i]即表示小于等于关键字b[i]的关键字个数，即b[i]的排名。题目中提示ord[]存储第二关键字排序的结果，此处应将处理结果保存到数组ord[]中，即ord[--cnt[b[i]]] = i。--cnt[b[i]保证了排名从0~n-1，同时，b[i]的出现次数减少一次。 空③，利用 cnt 数组统计第一个关键字的数量，所以次空应填：cnt[a[i]]++。 空④，通过上面代码cnt[i + 1] += cnt[i];，cnt[i]存储了小于等于i的第一关键字的个数，cnt[a[i]]即表示小于等于关键字a[i]的关键字个数，即a[i]的排名。cnt[a[ord[i]]]表示排名为i的第二关键字在数组位置ord[i]，其对应的双关键字的排名为cnt[a[ord[i]]]，它所在数组的位置为ord[i]。所以此空应填：res[--cnt[a[ord[i]]]] = ord[i]。 空⑤，数组 res[] 存储双关键字排序的结果，所以次空应填：a[res[i]], b[res[i]]。
