CF 782 B CoB. The Meeting Place Cannot Be Change 3分求极值

2019-11-06 06:43:24

字体：大中小

来源：转载

供稿：网友

题目链接：见这里题意：开始每个人都在一条数轴上的某个位置上，位置大于等于1都是整数，每个人有个最大移动速度，为在数轴上面哪个点集合，所用的集合时间最短，求这个时间，集合地点可以不是整数。解法：3分位置然后求极值。check就是对于每个位置，每个人以最大速度跑到的时间的最大值

#include <bits/stdc++.h>using namespace std;const int maxn = 6e5+10;int n;double x[maxn], v[maxn];double check(double p){ double t = 0; for(int i = 1; i <= n; i++) t = max(t, fabs(x[i] - p) / v[i]); return t;}int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) cin >> x[i]; for(int i = 1; i <= n; i++) cin >> v[i]; double l = 0, r = 1e10; int t = 1000; while(t--){ double mid = (l + r) / 2; double midd = (mid + r) / 2; if(check(mid) < check(midd)) r = midd; else l = mid; } PRintf("%.8f/n", check(l)); return 0;}

上一篇：Leetcode038--二叉树的层序遍历

下一篇：[LeetCode]463. Island Perimeter