题解：P12101 [NERC2024] Judicious Watching

NBRT_Line7 · 2025-04-25 19:50:26 · 题解

双倍经验：CF2052J。

一道反悔贪心题。

因为保证有一种次序能完成所有作业，所以首先我们按照截止时间排序。

考虑到以下两种情况：

• 写完作业再看剧。
• 看完剧再写作业。

如果看完剧再写作业还能在截止时间之前交上的话，我们显然先看剧。

所以我们要尽早看完所有剧集。

我们可以先进行初始化，然后离线查询。

我们可以记录下所有剧集的结束时间。

先把第 i 份作业截止时间与做前 i 份作业需要时间的差求出来。

• 若能看一部剧，那就看。
• 若差为负数怎么办？这时候，我们就要反悔，把上次的剧撤销掉。

时间复杂度：O(n+m+q \log n)，能通过。

#include<bits/stdc++.h>
#define int long long
//#define DEBUG
using namespace std;
const int N=2e5+10;
int n,m,q,b[N],x,c[N];
struct node{
    int a,b;
}a[N];
bool cmp(node a,node b){
    return a.b<b.b;
}
void solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) cin>>a[i].a;
    for(int i=1;i<=n;i++) cin>>a[i].b;
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(a+1,a+n+1,cmp);
    int t=0,i=1,j=1;
    while(i<=n){
        while(j>0&&t+a[i].a>a[i].b){
            j--;
            t-=b[j];
            c[j]=1e9;
            #ifdef DEBUG
            cout<<i<<' '<<j<<' '<<c[j]<<'\n';
            #endif
        }
        while(j<=m&&t+b[j]<=a[i].b-a[i].a){
            t+=b[j];
            c[j]=t;
            #ifdef DEBUG
            cout<<i<<' '<<j<<' '<<c[j]<<'\n';
            #endif
            j++;
        }
        t+=a[i].a;
        i++;
    }
    while(j<=m){
        t+=b[j];
        c[j]=t;
        j++;
    }
    #ifdef DEBUG
    for(int i=1;i<=m;i++) cout<<c[i]<<" ";
    cout<<'\n';
    #endif
    while(q--){
        cin>>x;
        cout<<upper_bound(c+1,c+m+1,x)-c-1<<' ';
    }
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();

    return 0;
}