HZU蓝桥杯校内第二次选拔赛题解
T1
题意： 从n nn个数中取最大的k kk个数。
对于80 8080%的数据，直接s o r t sortsort取最大的k kk个数,时间复杂度：O ( n l o g ( n ) ) O(nlog(n))O(nlog(n))，或者使用优先队列维护k kk个最大值时间复杂度：O ( n l o g ( k ) ) O(nlog(k))O(nlog(k))。
对于100 100100%的数据，根据快速排序分治思路，选取一个数作为基准k e y keykey，如果超过k kk个数比k e y keykey大，就往大于k kk的一边递归，如果没有超过k kk个数比k e y keykey大，就往小一边递归，而且比k e y keykey大的数都在里面。所以我们可以在期望时间复杂度：O ( n ) O(n)O(n)。
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=5e6+5; const int maxm=1e6; ll sum; int a[maxn]; ll q_sort(int l, int r, int k) { if (l > r) { return 0; } int p = rand() % (r - l + 1) + l; int x = a[p]; swap(a[r], a[p]); int i = l, j = r; while(i < j) { while(i < j && a[i] < x) i++; if(i < j) { swap(a[i],a[j]); j--; } while(i < j && a[j] > x) j--; if(i < j) { swap(a[i],a[j]); i++; } } swap(a[i], x); ll sum = 0; for (int j = i; j <= r; j++) sum += a[j]; if (r - i >= k) { sum = q_sort(i + 1, r, k); } else if (k > r - i + 1) { sum += q_sort(l, i - 1, k - (r - i + 1)); } return sum; } int main() { int n, k; srand(time(0)); scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } printf("%lld\n", q_sort(1, n, k)); return 0; }
