【CF1512F Education】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16365234.html

题目链接

题目

有一个长度为 $n$ 的数组 $a$ 和一个长度为 $n−1$ 的数组 $b$ ，初始位置为 $pos=1$ ，每一天可以选择得到 $a_{pos}$ 元钱，或者花费 $b_{pos}$ 元钱（钱数不能为负）使得 $pos\leftarrow pos+1$

现在希望买一台 $c$ 元的电脑，最少需要多少天。

Polycarp is wondering about buying a new computer, which costs $ c $ tugriks. To do this, he wants to get a job as a programmer in a big company.

There are $ n $ positions in Polycarp’s company, numbered starting from one. An employee in position $ i $ earns $ a[i] $ tugriks every day. The higher the position number, the more tugriks the employee receives. Initially, Polycarp gets a position with the number $ 1 $ and has $ 0 $ tugriks.

Each day Polycarp can do one of two things:

If Polycarp is in the position of $ x $ , then he can earn $ a[x] $ tugriks.
If Polycarp is in the position of $ x $ ( $ x < n $ ) and has at least $ b[x] $ tugriks, then he can spend $ b[x] $ tugriks on an online course and move to the position $ x+1 $ .

For example, if $ n=4 $ , $ c=15 $ , $ a=[1, 3, 10, 11] $ , $ b=[1, 2, 7] $ , then Polycarp can act like this:

On the first day, Polycarp is in the $ 1 $ -st position and earns $ 1 $ tugrik. Now he has $ 1 $ tugrik;
On the second day, Polycarp is in the $ 1 $ -st position and move to the $ 2 $ -nd position. Now he has $ 0 $ tugriks;
On the third day, Polycarp is in the $ 2 $ -nd position and earns $ 3 $ tugriks. Now he has $ 3 $ tugriks;
On the fourth day, Polycarp is in the $ 2 $ -nd position and is transferred to the $ 3 $ -rd position. Now he has $ 1 $ tugriks;
On the fifth day, Polycarp is in the $ 3 $ -rd position and earns $ 10 $ tugriks. Now he has $ 11 $ tugriks;
On the sixth day, Polycarp is in the $ 3 $ -rd position and earns $ 10 $ tugriks. Now he has $ 21 $ tugriks;
Six days later, Polycarp can buy himself a new computer.

Find the minimum number of days after which Polycarp will be able to buy himself a new computer.

思路

从前往后枚举每个位置，设其为整个过程到达的最右的位置。

枚举的过程可以记录当前过程中 $a_i$ 的最大值，然后当前过程中加的话只加这个词。

到达每个位置后在计算一下当前要达到 $c$ 的最小值，最后再取个最小值就是答案。

Code

// Problem: CF1512F Education
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1512F
// Memory Limit: 250 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 200010
//#define M
//#define mo
int n, m, i, j, k, T; 
int a[N], b[N], d, s, ans, mx, c; 

int Z(int x, int y)
{
	return x/y+(x%y ? 1 : 0); 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	T=read(); 
	while(T--)
	{
		d=-1; s=mx=0; ans=0x7fffffff; 
		n=read(); c=read(); 
		for(i=1; i<=n; ++i) a[i]=read(); 
		for(i=2; i<=n; ++i) b[i]=read(); 
		for(i=1; i<=n; ++i)
		{
			if(s<b[i]) d+=Z(b[i]-s, mx), s+=Z(b[i]-s, mx)*mx; 
			++d; s-=b[i]; mx=max(mx, a[i]); 
			if(s<c) ans=min(ans, d+Z(c-s, mx)); 
			// printf("%lld %lld %lld\n", s, d, ans); 
		}
		printf("%lld\n", ans); 
	}
	return 0;
}