题解：P15573 [USACO26FEB] Clash! S

· · 题解

我来比较仔细地讲一下循环部分。
题目要求：在每个整数时间点，FJ 可以选择打出一张手牌，前提是其花费不超过 FJ 当前的魔力值，打出后 FJ 当前的魔力值减去该牌的花费。 如果 FJ 手中至少有一张胜利条件牌，那么他接下来必须打出一张胜利条件牌。
先来考虑出牌的策略，当手里有至少一张胜利牌时，FJ会显然会出胜利牌中花费最小的（花费小，还可以使它更快回到牌堆）。当手里没有胜利牌时，他需要出一张花费最小的，来尽快抽取下一张牌。
由此我们得到了模拟的思路：使用一个优先队列模拟手牌（可以用 pair<bool,int> ,也可以自定义结构体并重载运算符 ），一个队列模拟牌堆。核心代码如下： ::::info[核心代码（结构体实现）]{open}

for(int i=1;i<=m;i++){
    sct_ tmp=pq.top();
    W+=tmp.w;
    pq.pop();
    q.push(tmp);

    pq.push(q.front());
    q.pop();
    if(tmp.s)
        cnt++;
    res2.push_back({W,cnt});       
}

::::
但这题 t\le 1\times 10^{18}，真的模拟这么多轮会超时，手玩样例，我们很自然地会想到有循环，也很自然地认为花费大的会留在手中不打，于是我们可以根据前文的贪心策略进行证明。

首先，当 k>N-H 时，手中时刻都会有至少一张胜利牌。按照规则，不可以出非胜利牌，于是非胜利牌一定留在手中，接下来，如果手中的胜利牌不止一张，还可以挑选。那么花费最大的几张胜利牌进入手中后就不会被打出。所以最终只有最小的 N-H+1 张胜利牌循环被打出。
当 k\le N-H 时，有时会出现手中没有胜利牌的状况。这时我们会打出花费最小的非胜利牌。可以证明，最大的 H-1 张非胜利牌永远不会被打出，依旧是另外的 N-H+1 张牌循环打出。
因此，我们证明了只会有 N-H+1 张牌循环打出。

当我们打出了 N-H 次，必定能让所有牌都进入过手中。接下来手牌就变得稳定，进入循环，再模拟 N-H+1 次记录循环内情况即可。实现时预处理模拟 O(N \log N)，询问用二分即可做到 O(Q \log N)。 ::::success[完整代码]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = double;
using lld = long double;
int n,h;
constexpr int N=2e5+5;
struct sct_{
    bool s;
    int w;
    bool operator < (const sct_& b) const{
        if(s!=b.s)  return s<b.s;
        return w>b.w;
    }
}a[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,h;
    cin>>n>>h;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
    }
    int k;
    cin>>k;
    for(int i=1;i<=k;i++){
        int id;
        cin>>id;
        a[id].s=1;
    }
    priority_queue<sct_>pq;
    queue<sct_>q;
    for(int i=1;i<=h;i++){
        pq.push(a[i]);
    }
    for(int i=h+1;i<=n;i++) 
        q.push(a[i]);
    vector<pair<ll,int> >res1;
    res1.reserve(n+1);
    res1.push_back({0,0});
    ll W=0,cnt=0;
    for(int i=1;i<=n-h;i++){
        sct_ tmp=pq.top();
        W+=tmp.w;
        pq.pop();
        q.push(tmp);

        pq.push(q.front());
        q.pop();
        if(tmp.s)
            cnt++;    

        res1.push_back({W,cnt});
    }
    int m=n-h+1;
    cnt=0,W=0;
    vector<pair<ll,int> >res2;
    res2.reserve(m+1);
    res2.push_back({0,0});
    for(int i=1;i<=m;i++){
        sct_ tmp=pq.top();
        W+=tmp.w;
        pq.pop();
        q.push(tmp);

        pq.push(q.front());
        q.pop();
        if(tmp.s)
            cnt++;
        res2.push_back({W,cnt});       
    }
    ll a=res1.back().first;
    int Q;
    cin>>Q;
    while(Q--){
        ll t;
        cin>>t;
        ll ans=0;
        if(t<=a){
            auto tmp=lower_bound(res1.begin(),res1.end(),pair<ll,int>{t+1,0});
            tmp--;
            cout<<(tmp->second)<<'\n';
        }
        else{
            t-=a;
            ans+=res1.back().second;
            ans+=(t/res2.back().first)*1ll*res2.back().second;
            t%=res2.back().first;
            auto tmp=lower_bound(res2.begin(),res2.end(),pair<ll,int>{t+1,0});
            tmp--;
            cout<<(ans+tmp->second)<<'\n';
        }
    }

    return 0;
}

::::