题解：P15573 [USACO26FEB] Clash! S

· · 题解

这是我这次 USACO 唯一切掉的一题，虽然写了这题以后就没写了，我太菜了！

分析

首先做这种题，一定要模拟样例。

一开始的序列为：

(2) 4 3
(5) 7 6

（序列上面是已有的元素，下方是即将抽取的，打括号的是必须先出的。）

第一步，先打出 2。消耗的时间就是 2。序列成为：

4 3 (5)
7 6 (2)

第二步，先打出 5。消耗的时间就是 5。序列成为：

4 3 7
6 (2) (5)

上面没有需要先打出的元素，又因为上方序列是无序的，我们要想让时间尽可能少，就要先打出时间最少的 3，这是很自然的。

第三步，打出 3，消耗时间 3。序列成为：

4 7 6
(2) (5) 3

第四步，打出 4，消耗时间 4。序列成为：

7 6 (2)
(5) 3 4

第五步打出 2，2 打完打 5，5 打完打 3，然后打 4……

有没有发现什么？从第四步以后就一直打出刚从下方取出的元素，出现了一个循环。

我们知道，一轮循环最多能把 n 个元素全取一遍（比如 k=0 时），所以我们只要模拟第一遍循环在通过计算就能完成了。

实现

对于模拟，我们可以用模拟样例的方法：用两个队列，第一个要按某种顺序，故使用优先队列；第二个用普通队列。对于周期，就是一个元素出优先队列两次。于是此部分时间复杂度为 \mathcal{O}(n \log n)。

对于答案计算，我们可以先算出在整循环里的答案，再加上最后一个可能不完整的周期答案，比较好实现，作者对于可能不完整的周期答案用了二分，于是此部分时间复杂度为 \mathcal{O}(q \log n)。

时间复杂度 \mathcal{O}((n+q)\log n)。

赛中代码

其中的 xw_qwq 是 @Neri_qwq 的曾用名，让我们一起膜拜她！

/*
Code by swate114514.
*/

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int _;

inline int read() {int s = 0, w = 1; char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') w *= -1;ch = getchar();}while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;}
inline ll readl() {ll s = 0, w = 1; char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') w *= -1;ch = getchar();}while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;}
inline void write(ll x) {if (x < 0) x = -x, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 2e5 + 5;
int n, h, q, a[N];
int k;
bool vis[N], mp[N];
struct node {
    int id, v, w;
    bool operator < (const node& o) const {
        if (w != o.w) return w < o.w;
        if (v != o.v) return v > o.v;
        return id > o.id; 
        // 按照下标顺序升序排，这样能让出现相同元素时先出下标小的。
        // 可以在这种情况下使循环长度更小（即复杂度更优）
    }
};

priority_queue<node> qu;
queue<node> qu2;
int cnt;
ll sum;
vector<ll> xw_qwq;

inline void check() {
    while (!qu.empty()) {
        int u = qu.top().id, v = qu.top().v, w = qu.top().w;
        qu.pop();
        if (mp[u]) break;
        else mp[u] = 1, sum += v;
        if (w) xw_qwq.push_back(sum), ++cnt;
        qu.push(qu2.front());
        qu2.pop();
        qu2.push({u, v, w});
    }
}

inline void solve() {
    n = read(), h = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    k = read();
    for (int i = 1; i <= k; ++i) vis[read()] = 1;
    for (int i = 1; i <= n; ++i) {
        if (i <= h) qu.push({i, a[i], vis[i]});
        else qu2.push({i, a[i], vis[i]});
    }
    check();
    q = read();
    while (q--) {
        ll t = readl();
        ll ans = t / sum * cnt;
        int x = upper_bound(xw_qwq.begin(), xw_qwq.end(), t % sum) - xw_qwq.begin();
        if (t % sum) write(ans + x);
        else write(ans);
        putchar('\n');
    }
}

int main() {
    // _ = read();
    _ = 1;
    for (int i = 1; i <= _; ++i) solve();
    return 0;
}