题解：P12000 扶苏出勤日记

awmc

题目大意

每天赚

b_i

块钱，

1

块钱可以换

a_i

个币去打乌蒙，求每天打乌蒙的最多次数。

题意分析

显然的二分，那么难点在于考虑 check。

check 能想到采用模拟思路，把

n

天遍历一边，先赚钱，然后换币。如果中途币不够了就 return 0，能过完这

n

天就 return 1。

考虑如何换币：假设

a_i<a_j

(i<j)

，而且第

i

天的币足以用到第

j

天，那么显然在第 $j$ 天换币比在第 $i$ 天换币更优。
更特别的，如果

j

离

i

最近，那么它们中间的日子换币一定比这两天换币更劣，考虑到这点，使用单调栈维护。

分类讨论，假设每天要打

x

把，现在是第

i

天，有

B

个币，

M

块钱，更优的下一天是

nxt_i

。

如果当前这一天是之后最优的一天，也就是说

nxt_i

不存在，那么把钱全部花光就好了，反正最优。

那一天存在的话，有

3

种情况：
第一：当前的币已经足够支撑到那一天，即

x\times(nxt_i-i)\le B

那么一块钱都不用花。

第二：花一部分钱可以使上面的式子成立，也就是说

x\times(nxt_i-i)\le B+M\times a_i

那么花最少的钱，因为剩下的要留给第

nxt_i

天。

第三：钱花完了也不能使上面的式子成立。
只能在这里把钱全部花完，因为留不到那一天，如果留给中间的日子反而劣，所以最好的是自己用完。

总的就上面几种情况，依次判断即可。

代码&细节

二分上界是

10^{12}

。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
int T,n;
int a[N],b[N],nxt[N];
int kkk;//第4种情况下花的钱

bool chk(int x){
	int now=0,B=0;
	for(int i=1;i<=n;i++){
		now+=b[i];
		int days=nxt[i]-i;
		if(nxt[i]==-1){ //当前最优
			B+=now*a[i];
			now=0;
		}else{
			if(now*a[i]>=x*days-B){ //钱够
				kkk=ceil(1.0*max(x*days-B,0ll)/a[i]); //计算最少需要花的钱
				B+=kkk*a[i];
				now-=kkk;
			}else{ //钱不够
				B+=now*a[i];
				now=0;
			}
		}
		if(B>=x)B-=x;
		else return 0;
	}
	return 1;
}

stack<int> s;
signed main(){
	ios::sync_with_stdio(0);cin.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];
		for(int i=1;i<=n;i++){ //维护单调栈
			while(!s.empty()&&a[s.top()]<=a[i]){nxt[s.top()]=i;s.pop();}
			s.push(i);
		}
		while(!s.empty())nxt[s.top()]=-1,s.pop();
		int l=0,r=1e12,mid;
		while(l<r){
			mid=(l+r+1>>1);
			if(chk(mid))l=mid;
			else r=mid-1;
		}
		cout<<l<<'\n';
	}
	return 0;
}

~~呜呜呜别卡我常~~

题解：P12000 扶苏出勤日记

文章操作

题目大意

题意分析

代码&细节

相关推荐

评论

题解：P12000 扶苏出勤日记