[NERC2019] Apprentice Learning Trajectory 题解

FFTotoro · 2025-07-06 20:21:10 · 题解

有一个较为简单的贪心策略：每次选取当前能选的、且锻造结束时间最早的一把剑制造。

直接暴力模拟时间复杂度不对，但是考虑到某位大师工作状态变化（开始 / 结束）的时间点最多有 2n 个，于是对于两个时间点之间直接选取锻造时间最短的剑“批量”锻造，直到它的结束时间超出了后一个时间点（这个可以用除法快速计算）。对于跨越某个时间点的锻造，考虑用 std::set 维护结束时间最早且可以锻造的剑，实现细节较多。时间复杂度 O(n\log n)。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,w=0; cin>>n;
  vector<int> p(n),ed(n);
  vector<tpi> s;
  for(int i=0;i<n;i++){
    int a,b; cin>>a>>b>>p[i];
    s.emplace_back(a,i,1),s.emplace_back(ed[i]=b,i,-1);
  } // 把所有事件离线存储
  sort(s.begin(),s.end());
  // 按照时间点排序
  vector<int> tmp(n,-1);
  set<pii> m,c;
  for(int e=0;e<n<<1;e++){
    auto [t,i,k]=s[e];
    if(!(e&&get<0>(s[e-1])==t)&&!m.empty()&&m.begin()->first<=t){
      w+=1+(t-m.begin()->first)/(c.begin()->first);
      // 计算一段时间内能锻造多少把剑
      int nt=t-(t-m.begin()->first)%c.begin()->first;
      // 求出批量锻造完所有剑后的时刻
      while(!m.empty())tmp[m.begin()->second]=-1,m.erase(m.begin());
      // 记得清空当前的 set
      while(!c.empty()){
        auto [x,y]=*c.begin();
        if(nt+x>ed[y])c.erase(c.begin());
        else{m.emplace(tmp[y]=nt+x,y); break;}
      } // 找可用的剑中结束时间最早的
    }
    if(k==1){
      m.emplace(tmp[i]=t+p[i],i);
      c.emplace(p[i],i);
    } // 加入
    else{
      if(~tmp[i])m.erase(m.find(make_pair(tmp[i],i)));
      c.erase(make_pair(p[i],i));
    } // 删除
  }
  cout<<w<<endl;
  return 0;
}