【算法小白周赛1D】K阶恒星系 - 题解和代码

题目链接：https://www.starrycoding.com/contest/3/D

题目描述

牛马座 A 是个巨大的椭圆星系，具有 $n$ 个恒星。和太阳系一样，每个恒星周围都有许多行星。侥幸团队通过太空望远镜，观测出每个恒星系里行星的数量，其中第 $i$ 个恒星系里有 $p_i$个行星。若第 $i$ 个恒星系为侥幸团队定义的 $k$阶恒星系，则在正整数序列 $(p_1,p_2,… p_n)
$中，$p_i$ 的左边和右边都至少有 $k$ 个元素的值小于 $p_i$

现在，侥幸团队请你统计出牛马座 A 中 $k$ 阶恒星系的数量。

输入格式

输入数据有 $2$ 行，第一行输入 $2$ 个正整数 $n,k$，分别表示恒星的数量和满足定义的 $k$ 值。

第二行：由 $n$ 个正整数构成的序列 $p_1,p_2,...,p_n$。

输出格式

一行一个正整数，表示牛马座 A 中$k$阶恒星系的数量。

样例

样例输入#1

10 2
8 8 10 7 4 8 2 1 7 4

样例输出#1

2

解释#1

加粗的数字代表$k$阶恒星系：8 8 10 7 4 8 2 1 7 4

样例输入#2

20 3
15 8 15 5 9 8 11 12 7 4 3 11 15 6 20 11 2 11 1 13

样例输出#2

5

数据范围

对于所有数据:

• $1000\le n\le 10^6$
• $50\le k\le 10^5$
• $1\le p_i\le n$

题解

题目大意：

有多少个数字前后都有$m$个数字比这个数字小。

做法一：优先队列

我们先讨论 $p_i$ 左侧的情况，右侧按照同样的逻辑做处理就可以了：

注意到，我们只关心有没有至少 k 个元素，而不关心是哪些元素小于 $p_i$。因此，我们可以贪心地维护到当前位置时，最小的 $k$ 个元素。如果这 $k$ 个元素中最大的数字小于 $p_i$，则说明可以选出 $k$个来。否则不满足，并且 $p_i$ 可以替换掉原来的$k$个元素中的最大数。

从上面可以看出，我们要动态地维护 $k$ 个元素，并且要频繁查询、删除最大值，和插入一个元素，用优先队列（大根堆）即可。

然后右侧同理。

时间复杂度$O(nlogn)$

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, k, p[N], ans;
bool f[N], g[N];
priority_queue<int> qf, qg;  // 维护到当前位置前最小的 k 个元素
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        if(qf.size() < k) qf.push(p[i]), f[i] = false;
        else if(p[i] > qf.top()) f[i] = true;
        else qf.pop(), qf.push(p[i]), f[i] = false;
    }
    for(int i = n; i >= 1; i--) {
        if(qg.size() < k) qg.push(p[i]), g[i] = false;
        else if(p[i] > qg.top()) g[i] = true;
        else qg.pop(), qg.push(p[i]), g[i] = false;
    }
    for(int i = 1; i <= n; i++) {
        if(f[i] && g[i]) ans++;
    }
    cout << ans;
    return 0;
}

做法二：树状数组

观察到我们只需要找$p_i$前后有多少个数字比自己大，很像一个求解逆序对问题，所以可以直接用树状数组

我们可以把所有的数字全部插入，设最大数为$maxn$，我们依次判断$a_i$前面即$query(a_i-1)$以及$a_i$后面即$query(maxn)-query(a_i)$是否含有$k$个数字，插入比较简单，单点插入权值为1的数字即可。

AC Code

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target ("avx")
#pragma GCC optimize ("inline")

#include <bits/stdc++.h>

#define ios_close std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr)

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
#define Pi  acos(-1.0)

template<typename T>
class BIT{
public:
    int sz;
    std::vector<T> t;

    BIT(){

    }

    BIT(int n){
        sz = n;
        t = std::vector<T>(sz + 1);
    }

    int lowbit(int x){
        return x & (-x);
    }

    void modfity(int x, T val){
        for(int i = x; i <= sz; i += lowbit(i)){
            t[i] += val;
        }       
    }

    T query(int x){
        T ans = 0;
        for(int i = x; i >= 1; i -= lowbit(i)){
            ans += t[i];
        }
        return ans;
    }
};

void solve(){
    int n, k;
    std::cin >> n >> k;
    BIT<int> pre(n);
    std::vector<int> a(n + 1);
    std::vector<int> l(n + 1);
    std::vector<int> r(n + 1);
    for(int i = 1; i <= n; i ++ ){
        std::cin >> a[i];
        l[i] = pre.query(a[i] - 1);
        pre.modfity(a[i], 1);
    }
    BIT<int> suf(n);
    for(int i = n; i >= 1; i -- ){
        r[i] = suf.query(a[i] - 1);
        suf.modfity(a[i], 1);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++ ){
        //std::cout << l[i] << " " << r[i] << '\n';
        if(l[i] >= k && r[i] >= k){
            //std::cout << i << '\n';
            ans ++;
        }
    }
    std::cout << ans;
}

int main(){
#if 0
    ios_close;
#endif

#if 1
    freopen("kgalaxy.in", "r", stdin);
    freopen("kgalaxy.out", "w", stdout);
#endif
    int T = 1;
#if 0
    std::cin >> T;
#endif

#if 0
    scanf("%d", &T);
#endif

    while(T -- ){
        solve();
    }
    return 0;
}

StarryCoding - 编程开发新手村，非常适合新手小白的一个网站，推荐给大家~

5月1日晚上还有一场入门教育赛，欢迎来玩：https://www.starrycoding.com/contest/5