AtCoder Beginner Contest 306 - E - Best Performances

Solost

2023 年 07 月 03 日

130 次浏览

暂无评论

2094字数

题目题解

## 题目链接

[链接](https://atcoder.jp/contests/abc306/tasks/abc306_e)

## 题目大意

题目意思是，长度为n的序列，q次询问，每次输入p,w把a[p]改成y,问你前k大的元素和是多少

## 题解

这个题目的难点是要每次修改元素后还要求序列的前k大，这就有点麻烦了，如果使用暴力不可能能过，n,k=5e5;所以使用新的一个STL容器`multiset`，这个容器和set的区别就是这个容器可以存储多个相同的元素。

还有要注意一个点，如果你要erase一个元素，不要这要移除，`y.erase(*x.begin())`，最好先用一个变量把`*x.begin()`存起来，例如`int t = *x.begin(), y.erase(t);`

```
std::multiset<int> s;    // 定义 int 类型的多重集 s
s.insert(x);             // 向 s 里面插入元素 x
s.erase(x);             // 删除 s 中所有等于 x 的元素
s.extract(x);           // 删除 s 中的某一个等于 x 的元素
```

我们需要每次询问后输出前k大元素的和。用一个set来为维护前k大元素x，另一个维护n-k元素y，每次将新元素插入y中，然后来计算，如果x的个数不够k个，从y中取，直到达到k个元素，如果够了，然后比较，有没有y中的元素大小还要比x的大，如果有就交换，每次计算一下总和就好，s不是重新算，而是减去了哪个元素，再加进来哪个元素。

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define p first
#define w second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 5e5 + 10;

int n, k, q;
ll s;
multiset<int> x, y;

void balance()
{
    while (x.size() < k) {
        auto iy = y.end();
        iy--;
        x.insert((*iy));
        s += (*iy);
        y.erase(iy);
    }
    if (y.empty() || x.empty())
        return;

while (1) {
        auto ix = x.begin();
        auto iy = y.end();
        iy--;
        int ex = (*ix);
        int ey = (*iy);
        int t = ey - ex;
        if (t <= 0) return;
        s += t;
        x.erase(ix);
        x.insert(ey);
        y.erase(iy);
        y.insert(ex);
    }
}

void add(int v)
{
    y.insert(v);
    balance();
}

void erase(int v)
{
    auto ix = x.find(v);
    if (ix != x.end()) {
        s -= v;
        x.erase(ix);
    } else
        y.erase(y.find(v));
    balance();
}

void solve()
{
    cin >> n >> k >> q;
    vector<int> a(n, 0);
    for (int i = 0; i < k; i++) {
        x.insert(0);
    }
    for (int i = k; i < n; i++) {
        y.insert(0);
    }

while (q--) {
        int p, w;
        cin >> p >> w;
        p--;
        add(w);
        erase(a[p]);
        a[p] = w;
        cout << s << endl;
    }
}
int main()
{
    IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 07 月 03 日