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

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

題目
略,請看原題

前言

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

想法

將士兵的能力排序後,二分搜最小的士兵能力,這樣不小於這個士兵能力的士兵全部都可以一起帶隊。
接下來只要能夠判斷一隊士兵能否走到(n+1)就好。
每次帶兵碰到一個陷阱,如果陷阱(_i)危險度(>)最低的士兵能力,那麼領隊就必須先到(r_i)去解鎖,然後觀察到,如果領隊解鎖完直接往回接士兵再往右走,那麼對於陷阱(_i),我們必須多走(2times(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

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/petjelinux/p/13595771.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!