题解：CF1260D A Game with Traps

Laisira · 2025-01-23 11:14:42 · 题解

思路

简单二分，显然选最大的几个人一定不劣，拆掉 i 陷阱有意义当且仅当所有 j，使得 d_j \leq d_i 被拆掉，二分拆陷阱的最小值，模拟跑一边就行了。

代码

#include<bits/stdc++.h>
#define int long long 
#define Maxn 400005 
using namespace std;
int a[Maxn];
struct node {
    int l,r,d;
    bool operator<(const node&is)
    const {return l != is.l?l < is.l:r < is.r;}
} e[Maxn],t[Maxn];
signed main()
{
    int m,n,k,t1;
    cin>>m>>n>>k>>t1;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    sort(a+1,a+1+m);
    for(int i=1;i<=k;i++)
        cin>>e[i].l>>e[i].r>>e[i].d;
    int l = 0,r = 4e5+5,mid;
    while(l < r) {
        int tot = 0;
        mid = (l+r)>>1;
        for(int i=1;i<=k;i++)
            if(e[i].d >= mid)
                t[++tot] = e[i];
        sort(t+1,t+1+tot);
        int ans = 0;
        for(int i=1;i<=tot;i++)  {
            int l1 = t[i].l,r1 = t[i].r;
//          cout<<i<<"|";
            while(i < tot&&t[i+1].l <= r1)r1 = max(r1,t[++i].r);
            ans += (r1-l1+1)*2;
//          cout<<l1<<" "<<r1<<"]\n";
        }
//      cout<<mid<<" "<<ans+n+1<<"\n";
        if(ans+n+1 <= t1)r = mid;
        else l = mid+1;
    } int maxn = 0;
    for(int i=1;i<=k;i++)
        if(e[i].d < l)
            maxn = max(maxn,e[i].d);
    l = 0,r = m;
    while(l < r) {
        mid = (l+r+1)>>1;
        if(a[mid] < maxn)l = mid;
        else r = mid-1;
    }
//  cout<<a[l]<<" "<<maxn<<" ";
    cout<<m-l;
    return 0;
}