求助 TLE#3
查看原帖
求助 TLE#3
561529
Infinite_Energy楼主2023/2/24 19:54

先放代码。

#include<bits/stdc++.h>
using namespace std;
long long n;
double l,r,mid,ans;
bool flag;
struct node{
	long long x,v;
}a[1000010];
bool check(double t){
	double maxx=-1000000000000;
	for(int i=1;i<=n;i++){
		if(a[i].v>0){
			maxx=max(maxx,a[i].x+t*a[i].v);
//			cout<<maxx<<endl;
		}else{
			double tmp=a[i].x+t*a[i].v;
//			cout<<tmp<<"!!!"<<endl;
			if(tmp<maxx){
				return true;
			}
		}
	}
	return false;
}
long long read(){
	char ch=getchar();
	long long sgn=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			sgn=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar();
	}
	return x*sgn;
}
void write(long long n,bool p){
	if(n<0){
		putchar('-');
		n=-n;
	}
	if(n==0){
		if(p==true){
			putchar('0');
		}
		return;
	}
	write(n/10,0);
	putchar(n%10+'0');
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].x,&a[i].v);
	}
	l=0;
	r=1000000007;
	while(fabs(l-r)>0.0000000001){
//		cout<<l<<" "<<r<<" "<<mid<<endl;
		mid=(l+r)/2;
		if(check(mid)){
			flag=1;
			ans=mid;
			r=mid;
		}else{
			l=mid;
		}
	}
	if(flag==0){
		printf("-1\n");
	}else{
		printf("%.10lf\n",ans);
	}
	return 0;
}

我发现#3的答案正好是1e9,于是调整二分上界,结果调成1e9+7就会炸掉,求调。

2023/2/24 19:54
加载中...