自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 23:11:54，当前版本为作者最后更新于2025-03-29 19:07:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

为了方便解题，对比太郎打怪兽的过程进行时光倒流：从后往前考虑每个时间段，下文中的 $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;
}