Codeforce 1260 D. A Game with Traps 解析(思維、二分搜)

今天我們來看看CF1260D
題目連結

題目
略，請看原題

前言

一開始想法方向對了，但是犯了個小錯誤，以為最多只要帶士兵兩次就好

<div class=“VVVcopyrightAAA”;>@copyright petjelinux 版權所有<br>
<a href=“https://www.cnblogs.com/petjelinux/”>觀看更多正版原始文章請至petjelinux的blog</a></div>

想法

將士兵的能力排序後，二分搜最小的士兵能力，這樣不小於這個士兵能力的士兵全部都可以一起帶隊。
接下來只要能夠判斷一隊士兵能否走到$n+1$就好。
每次帶兵碰到一個陷阱，如果陷阱$_i$危險度$>$最低的士兵能力，那麼領隊就必須先到$r_i$去解鎖，然後觀察到，如果領隊解鎖完直接往回接士兵再往右走，那麼對於陷阱$_i$，我們必須多走$2\times(r_i-l_i+1)$($+1$是因為士兵會在陷阱前一格等)格。而如果後面有個有作用的陷阱$_c$(危險度$>$最低的士兵能力)的區段$[l_c,r_c]$和之前的陷阱$_i$的區段$[l_i,r_i]$有重疊，那麼我們當然希望能夠先兩個陷阱都解除以後再帶士兵走過去，否則就要多走兩次$[l_c,r_c]\bigcap[l_i,r_i]$。

實作細節:我在檢查一隊士兵能否走過$n+1$格時，$res$為所有有作用的陷阱的區段的交集的長度，並且維護$minl$和$maxr$代表目前維護的陷阱的區段的交集的左界右界，當下一個有作用的陷阱$_i$的$l_i>maxr$時代表我們已經完成維護一個要走兩遍的區段。

程式碼:

const int _n=2e5+10,MAXB=19;  
int t,n,m,k,tt,a[_n],l,r,d;  
struct K{int l,r,d;  
  bool operator<(const K& rhs)const{return l<rhs.l;}  
} ks[_n];  
bool ok(int low){  
  int res=0,maxr=0,minl=1; //讓maxr-minl+1==0  
  rep(i,0,k){  
    if(ks[i].d>low and ks[i].l<=maxr)maxr=max(maxr,ks[i].r);  
    else if(ks[i].d>low and ks[i].l>maxr)res+=maxr-minl+1,minl=ks[i].l,maxr=ks[i].r;  
  }res+=maxr-minl+1;  
  return n+1+res*2<=t;  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>m>>n>>k>>t;rep(i,0,m)cin>>a[i];rep(i,0,k){cin>>l>>r>>d;ks[i]={l,r,d};}  
  sort(a,a+m),sort(ks,ks+k);  
  int ans=-1;per(j,0,MAXB)if((ans+(1<<j))<m and !ok(a[ans+(1<<j)]))ans+=(1<<j);  
  cout<<m-1-ans<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission