cf1512F. Education

cf1512F. Education

题意:

小明想买一个价值为c的东西,他开始打工,他一开始在第i个职务,每天可以挣a[i],他也可以用一天的时间并且花费b[i]升到i+1职务,第i+1职务每天可以挣a[i+1]
一共有n个职务,问他最少要多少天才能攒够钱c
2<=n<=2e5

题解:

看看数据范围。。这题直接暴力就行emm
我们直接计算在第i个岗位挣到c需要多少钱,取最小值
因为岗位需要一步一步升,所以到第i个岗位时,要计算好升到第i个岗位所需要的时间,以及当前的钱
详细看看代码,注意细节就行
(比赛时都没看到这题)

代码:

#include<bits/stdc++.h>
#define debug(x,y) printf("%s = %d\n",x,y);
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=2e5+9;
ll a[maxn];
ll b[maxn];
int main()
{
	int t;
	cin>>t;
	while(t--){
		ll n,c;
		cin>>n>>c;
		ll minn=1e13+9;
		for(int i=1;i<=n;i++)a[i]=0;
		for(int i=1;i<n;i++)b[i]=0;
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		for(int i=1;i<n;i++)scanf("%lld",&b[i]);
		ll tot=0;
		ll preday=0;
		ll pretot=0;
		for(int i=1;i<=n;i++)
		{
			tot=preday+ceil(1.0*(c-pretot)/(1.0*a[i]));//到此为止 
			ll w=ceil(1.0*(b[i]-pretot)/(1.0*(a[i])));//晋升所需要的天数 
			preday+=w+1;
			pretot+=(w*a[i])-b[i];
			minn=min(tot,minn);
		}
		printf("%d\n",minn); 
	} 
}

上一篇:2021团体程序设计天梯赛 L1-7 天梯赛的善良


下一篇:2018NOIP集训-5 货物运输(倍增)