【 Gym - 101138F 】GukiZ Height （数学）

题意

初始高度0，目标值h，第i天目标值会下降i，当前高度会改变a[i%n]，求高度不小于目标值的最早的时间。

题解

假设最早时间是bn k天，那么

(h-(bn k) (bn k 1)/2 le bs[n] s[k])

化成关于b的一元二次不等式，求根公式可以求得最小的整数解。 但是要用long double，否则会WA。

代码

代码语言：javascript复制

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#define N 100005
#define ll long long
#define ld long double
using namespace std;
ll n,h,a,s[N],ans=1LL<<60;
int main() {
	scanf("%lld%lld",&n,&h);
	for(int i=0;i<n;i  ){
		scanf("%lld",&a);
		s[i 1]=s[i] a;
	}
	for(ll i=1;i<=n;i  ){
		if(h-i*(i 1)/2<=s[i]){
			ans=i;
			break;
		}else{
			ld a=n*n,b=(ld)2*i*n n 2*s[n],c=(ld)i*i i-2*h 2*s[i];
			ans=min(ans,(ll)ceil((-b sqrtl(b*b-a*c*4))/(a*2))*n i);
		}
	}
	printf("%lldn",ans);
	return 0;
}

double

0 人点赞