HZU蓝桥杯校内第二次选拔赛题解

简介: HZU蓝桥杯校内第二次选拔赛题解

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;
}
相关文章
|
4月前
|
人工智能 测试技术 C++
蓝桥杯15届第二次模拟赛C/C++详解
蓝桥杯15届第二次模拟赛C/C++详解
104 0
|
4月前
|
C++
蓝桥杯15届第二次模拟C++
蓝桥杯15届第二次模拟C++
31 0
|
Java
2020年4月蓝桥杯第二次模拟赛解题报告(本科组)Java语言 第三题
2020年4月蓝桥杯第二次模拟赛解题报告(本科组)Java语言 第三题
69 0
|
3月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
57 0
|
3月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
42 0
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
40 0
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
50 0
|
3月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
44 0
|
3月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
27 1
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
45 0