Cf Round #403 B. The Meeting Place Cannot Be Changed(二分答案)

时间：2023-03-08 20:44:35

The Meeting Place Cannot Be Changed

我发现我最近越来越zz了,md 连调程序都不会了,首先要有想法,之后输出如果和期望的不一样就从输入开始一步一步地调啊,tmd现在输出不一样就知道在那等着,有毛用啊.

【题目链接】The Meeting Place Cannot Be Changed

【题目类型】二分答案

&题解：

二分时间,判断函数比较难想,要先假设所有人都向左走,找到坐标最大的那个,之后在假设所有人都向右走,找到坐标最小的那个,如果最大的<=最小的就行了

&代码：

#include <cstdio>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

using ll=long long;

const int maxn= 6e4 +9;

int n,x[maxn],v[maxn];

double eps = 1e-6;

bool ok(double t)

{

	double ma=-2e9,mi=2e9;

//	printf("mi=%f\n",mi);

	for(int i=0;i<n;i++){

		ma=max(ma,x[i]-v[i]*t);

		mi=min(mi,x[i]+v[i]*t);

//		printf("i=%d x[i]=%d  v[i]=%d mi=%f\n",i,x[i],v[i],mi);

	}

//	printf("ma %f mi %f\n",ma,mi);

	return ma<=mi;

}

int main()

{

//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	//freopen("C:\\Users\\Zmy\\Desktop\\in.txt", "r", stdin);

	scanf("%d",&n);

	for(int i=0;i<n;i++) scanf("%d",&x[i]);

	for(int i=0;i<n;i++) scanf("%d",&v[i]);

	double l=0,r=1e9;

	while(l-r<=eps){

		double mid=(l+r)/2;

		if(ok(mid)) r=mid-eps;

		else l=mid+eps;

	}

	printf("%.7f\n",l);

	return 0;

}