自动搬运

查看原文

来自洛谷，原作者为

	OIer_Hhy 已退役

搬运于2025-08-24 23:12:45，当前版本为作者最后更新于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;
}