心情复杂。。。知识积累太少。。没想到能用nth_element； 只要注意：nth_element(a, a + b[i].k, a + b[i + 1].k); 不要选取全部，不然会tle
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; struct node { int id, k; bool operator<(const node &a)const { return k < a.k; } }b[105]; unsigned a[10000009]; int n, m; unsigned x, y, z, ans[105]; 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; } int main() { int cas = 0; while (~scanf("%d%d%u%u%u", &n, &m, &x, &y, &z)) { for (int i = 0; i < m; i++) scanf("%d", &b[i].k), b[i].id = i; for (int i = 0; i < n; i++){a[i] = rng61();} sort(b, b + m); b[m].id = m; b[m].k = n; for (int i = m - 1; i >= 0; i--) { nth_element(a, a + b[i].k, a + b[i + 1].k); ans[b[i].id] = a[b[i].k]; } printf("Case #%d:", ++cas); for (int i = 0; i < m; i++) printf(" %u", ans[i]); printf("\n"); } return 0; }