[JOIST 2025 Day3] 勇者比太郎 3 题解

· · 题解

很好的题目，使我的比太郎打怪兽。

为了方便解题，对比太郎打怪兽的过程进行时光倒流：从后往前考虑每个时间段，下文中的 S_i 表示原题面中的 T-S_i。假设时刻从 0 开始，令“第 i 个时间段”为时刻 [i-1,i] 中的这一段时间，本文中 S_i 表示“比太郎可以在前 S_i 个时间段内攻击怪兽 i”（对应到原题面中即为“后 S_i 个时间段”，因为进行了时光倒流），也可以理解为“第 i 个怪兽在第 S_i 个时间段之后将其剩余 HP 加入罚分，该怪兽消失”。

先忽略 P 的限制，即先考虑 \forall i,P_i=1 的情况。对于单个 \ell 的答案很好计算，有一个贪心策略：按照 S_i 从小到大排序（接下来的讨论中均默认 S_1\le S_2\le\cdots\le S_N），先处理 S_i 较小的怪兽直到它消失；由于每个怪兽的权值相同，所以该策略正确。但是对于多个 \ell 的答案，我们需要找到更高效的计算方法。

这里先给出结论。不妨认为 S_0=H_0=0；对于一个 \ell，在最优策略下，最小罚分（即最小剩余的 HP）为：

\max\limits_{i=0}^N\left(\sum\limits_{j=0}^i\ell\cdot H_j-S_i\right)

证明（自己搓的，如果有问题请在评论区指出）：

这个值必然是答案的一个下界，因为只考虑前 i 个怪兽时，最多也只能打掉 S_i 的 HP（怪兽在这之后会消失），产生剩下的罚分是不可避免的。下面证明这个值也是答案的上界。

记 C_{l,r}=\sum\limits_{i=l}^rH_i。不妨认为上述的值在 i=k 时取最大值，那么：

  • 对于 j>k，有 \ell\cdot C_{0,k}-S_k\ge \ell\cdot C_{0,j}-S_j，变形得到 S_j-S_k\ge\ell\cdot C_{j+1,k}，所以后面的时间足够，剩余怪兽的 HP 均能全部解决，不会有更多的罚分。
  • 对于 j\le k，考虑贪心策略的性质：比太郎处理怪兽 1\sim k 的时间必然是一段前缀，只要这段前缀长度 \ge S_k，那么必然不会有更多的罚分。如果这段前缀长度 <S_k，分两种情况讨论
    • 如果 S_{k-1}+\ell\cdot H_k<S_k\Leftrightarrow\ell\cdot C_{0,k}-S_k<\ell\cdot C_{0,k-1}-S_{k-1}，这样就与一开始的假设（原式在 i=k 处取到最大值）矛盾了！
    • 否则，考虑这个贪心策略中什么时候开始处理第 k 个怪兽，由于上面的条件不成立，又由于前缀长度 <S_k，所以处理第 k 个怪兽必须在第 S_{k-1} 个时间段或更早开始；于是又可以用上面的方法讨论第 k-1 个怪兽……如此往复直到出现矛盾。可以证明矛盾一定出现，因为处理第 1 个怪兽的开始时间不可能严格小于第一个时间段。

综上，该结论成立。

接下来沿用证明中 C_{l,r} 的定义。答案式子可以改写为 \max\limits_{i=0}^N\left(C_{0,i}\cdot\ell-S_i\right)，发现这是一堆一次函数的最大值（y=C_{0,i}\cdot x-S_i），又由于 C_{0,i} 随 i 增大而增大，所以直接单调栈维护下凸壳即可。如果没有学过这方面知识，请右转学习斜率优化。预处理这个凸壳的时间复杂度 O(N)，然后凸壳上每一条线段 y=kx+b(x\in[l,r)) 都对应了一个区间 \ell\in[l,r)，相当于这些 \ell 的答案就为 k\cdot\ell+b；由于是区间修改，并且这个东西具有可差分性，所以直接差分维护修改，最后跑一遍 O(L) 的前缀和。

考虑当不满足 \forall i,P_i=1 的时候该怎么做。观察到贪心策略只需要一个修改，即必须先保证 P_i 较大的尽量被处理完（注意，不一定是优先处理）；那么如何转化成原问题？设将序列 P_i 从小到大排序接着去重后的序列为 P'=\{P'_1,P'_2,\ldots,P'_{|P'|}\}，并使 P'_0=0，只需要枚举一个阈值 X=P'_i(1\le i\le|P'|)，将所有 P_i\ge X 的怪兽拉出来跑一遍上面的算法，给这一个阶段求出的凸壳上所有线段的 k 与 b 都乘上权值 P_i-P_{i-1}（相当于计算“尽量保证处理完”得到的贡献），直接按照原来的方式把差分标记打上去即可。

最后对于 Q 个询问二分求解。总的时间复杂度为 O(N^2+L+Q\log L)。

代码实现是较为简洁的。放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
inline int cd(int x,int y){
  return x/y+!!(x%y);
}
inline int crs(pii x,pii y){
  return cd(x.second-y.second,y.first-x.first);
} // 求出两条线段的交点的 x 坐标
inline pii operator +(pii x,pii y){
  return make_pair(x.first+y.first,x.second+y.second);
}
inline pii operator -(pii x,pii y){
  return make_pair(x.first-y.first,x.second-y.second);
}
inline pii operator *(pii x,int y){
  return make_pair(x.first*y,x.second*y);
}
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,L,t; cin>>n>>L>>t;
  vector<tpi> a(n);
  vector<int> pl;
  for(auto &[s,h,p]:a)
    cin>>s>>h>>p,s=t-s,pl.emplace_back(p);
  sort(a.begin(),a.end());
  sort(pl.begin(),pl.end());
  pl.erase(unique(pl.begin(),pl.end()),pl.end());
  vector<pii> rs(L+2);
  for(int i=0;i<pl.size();i++){
    vector<pii> st={make_pair(0,0)};
    int c=0;
    for(auto [s,h,p]:a)
      if(p>=pl[i]){
        pii l(c+=h,-s);
        while(st.size()>1&&crs(st[st.size()-2],st.back())>=crs(st.back(),l))
          st.pop_back();
        st.emplace_back(l);
      } // 用单调栈把凸壳求出来
    int w=pl[i]-(i?pl[i-1]:0);
    for(int j=0;j<st.size();j++){
      int l=0,r=L+1;
      if(j)l=max(l,crs(st[j-1],st[j]));
      if(j+1<st.size())r=min(r,crs(st[j],st[j+1]));
      if(l<r)rs[l]=rs[l]+st[j]*w,rs[r]=rs[r]-st[j]*w;
    } // 差分区间修改打标记
  }
  for(int i=1;i<=L;i++)
    rs[i]=rs[i-1]+rs[i];
  int q; cin>>q;
  while(q--){
    int lm,l=0,r=L; cin>>lm;
    while(l<r){
      int m=l+r+1>>1;
      if(rs[m].first*m+rs[m].second<=lm)l=m;
      else r=m-1;
    } // 二分求解最大的级别
    cout<<l<<'\n';
  }
  return 0;
}