专栏文章

题解：P12000 扶苏出勤日记

哈哈哈人生
P12000题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miprqxgj
此快照首次捕获于
2025/12/03 16:52
3 个月前
此快照最后确认于
2025/12/03 16:52
3 个月前
查看原文

题外话

不知道为什么，赛时第一感觉就是 ST 表，全然忘了单调队列。但理论上 ST 表也是 O(nlog⁡n)O(n\log n)，和单调队列没区别。但可能是被卡常了吧就是没过去（8080 分），本文最后有我没过的 ST 表代码，请大佬们看看出了什么问题。

思路

首先观察到答案有单调性，可以二分答案。分别枚举每一天的花钱情况。假设我们有第 ii 天的收入 xx 元，在第 jj 天我们可以最多得到 x×max⁡k=ijakx\times \max^{j}_{k=i} a_k。所以我们可以以此贪心。而 max⁡k=ijak\max^{j}_{k=i} a_k 这个东西，我的第一反应是 ST 表，但却不知为何超时。再次转变思路，发现我们发现最大值是单调递增的，所以一定是第 ii 天的钱花完后我们再去花第 i+1i+1 天的钱，所以 ii 的变化是每次加一。而 jj 是我们枚举的，也是每天加一。这个不就是滑动窗口（单调队列模板）吗？所以最终复杂度 O(nlog⁡n)O(n\log n)，瓶颈在二分。

代码

正解代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[1000005],b[1000005],c[1000005],q[1000005];
bool check(int x){
	for(int i=1;i<=n;i++)c[i]=b[i];
	int jl=1,ys=0,h=0,r=-1;
	for(int i=1;i<=n;i++){
		while(h<=r&&a[q[r]]<=a[i])r--;
		q[++r]=i;
		int y=x;
		if(y<=ys)ys-=y,y=0;
		else y-=ys,ys=0;
		while(jl<=i&&y>0){
		    int tmp=min((int)ceil(1.0*y/a[q[h]]),c[jl]);
			y-=tmp*a[q[h]];
			c[jl]-=tmp;
			if(c[jl]==0){
				if(q[h]==jl)h++;
				jl++;
			}
		}
		if(y>0)return 0;
		ys+=-y;
	}
	return 1;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>b[i];
		int l=0,r=1e12,mid,ans=0;
		while(l<=r){
			mid=(l+r)/2;
			if(check(mid))ans=mid,l=mid+1;
			else r=mid-1;
		}
		cout<<ans<<"\n";
	}
	return 0;
}
ST 表 8080 分代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef int type;
inline int read(){
	int x=0,f=1;
	char ch=getchar_unlocked();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar_unlocked();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar_unlocked();
	}
	return x*f;
}
inline void write(long long x){
	if(x<0)putchar_unlocked('-'),x=-x;
	if(x>9)write(x / 10);
	putchar_unlocked(x%10+'0');
}
int t,n,a[1000005],b[1000005],c[1000005],LOG[1000005],ST[1000005][25];
void build_log(){
	LOG[0]=-1;
	for(int i=1;i<=1000000;i++)LOG[i]=LOG[i/2]+1;
}
void build_st(){
	for(int i=1;i<=n;i++){
		ST[i][0]=a[i];
	}
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			ST[i][j]=max(ST[i][j-1],ST[i+(1<<j-1)][j-1]);
		}
	}
}
int find(int l,int r){
	int w=LOG[r-l+1];
	return max(ST[l][w],ST[r-(1<<w)+1][w]);
}
bool check(int x){
	for(int i=1;i<=n;i++)c[i]=b[i];
	int jl=1,ys=0;
	for(int i=1;i<=n;i++){
		int y=x;
		if(y<=ys)ys-=y,y=0;
		else y-=ys,ys=0;
		while(jl<=i&&y>0){
		    int tmp=min((int)ceil(1.0*y/find(jl,i)),c[jl]);
			y-=tmp*find(jl,i);
			c[jl]-=tmp;
			if(c[jl]==0)jl++;
		}
		if(y>0)return 0;
		ys+=-y;
	}
	return 1;
}
signed main() {
    build_log();
	t=read();
	while(t--){
		n=read();
		for(int i=1;i<=n;i++)a[i]=read();
		for(int i=1;i<=n;i++)b[i]=read();
	    build_st();
		int l=0,r=1e12,mid,ans=0;
		while(l<=r){
			mid=(l+r)/2;
			if(check(mid))ans=mid,l=mid+1;
			else r=mid-1;
		}
		write(ans),putchar('\n');
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...