题意
将一个函数运行 n 次，一共得到 n 个值，有 m 次询问，每次询问第 k 小的值。
分析
考察了 \(nth\_element\) 函数的运用。\(nth\_element(a, a + x, a + n)\) 使得 （ \(a\) 数组下标范围 \([0, n)\) ） \(a[x]\) 存的是第 \(x\) 小的数，且保证 \(x\) 左边的数小于等于它，右边的数大于等于它（ 当 \(x = 0\) 时， \(a[0]\) 是最小的值 ）。
将 \(k\) 排序后从大到小，求值，并更新 \(n\) 的值，因为右边的数一定大于等于左边的数，剩下第 k 小的取值一定能在左边取到。code
#include#include #include #include #include using namespace std;typedef long long ll;const int MAXN = 1e7 + 10;int kase = 1;int n, m;unsigned A, B, C;unsigned x, y, z;unsigned rng61() { unsigned t; x ^= x << 16; x ^= x >> 5; x ^= x << 1; t = x; x = y; y = z; z = t ^ x ^ y; return z;}unsigned a[MAXN];struct B { int x, i; bool operator<(const B&other) const { return x > other.x; }}b[105];unsigned ans[105];int main() { while(~scanf("%d%d%u%u%u", &n, &m, &A, &B, &C)) { x = A; y = B; z = C; for(int i = 0; i < n; i++) { a[i] = rng61(); } for(int i = 0; i < m; i++) { scanf("%d", &b[i].x); b[i].i = i; } sort(b, b + m); int len = n; for(int j = 0; j < m; j++) { if(j && b[j].x == b[j - 1].x) { ans[b[j].i] = ans[b[j - 1].i]; continue; } nth_element(a, a + b[j].x, a + len); ans[b[j].i] = a[b[j].x]; len = b[j].x; } printf("Case #%d:", kase++); for(int i = 0; i < m; i++) { printf(" %u", ans[i]); } printf("\n"); } return 0;}