【题目链接】:http://codeforces.com/contest/782/PRoblem/B
【题意】 每个人都有一个速度,只能往上走或往下走; 然后让你找一个地方,所有人都能够在t时间内到达; 让t最小.
【题解】 很明显的二分了; 二分时间t; 对于某个时间t,这个人都有一个能够到达的唯一区间 [x[i]-v*t..x[i]+v*t] 如果所有人的区间都有交集. 那么就能在那些交集里面随便选一个点了; 区间的交集可以用 最大的左端点小于等于最小的右端点这个依据来判断是否存在 想让答案的精度高一点,就让程序的二分多做几次就好; 固定200次就够了 【完整代码】
#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int, int> pii;typedef pair<LL, LL> pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int N = 6e4+100;int x[N], v[N];int n;int main(){ //freopen("F://rush.txt", "r", stdin); rei(n); rep1(i, 1, n) rei(x[i]); rep1(i, 1, n) rei(v[i]); double l = 0, r = 1e9 + 100,ans = 0; rep1(j,1,200) { double m = (l + r) / 2; double ll = -1e18, rr = 1e18; rep1(i, 1, n) { double t1 = x[i] - m*v[i], t2 = x[i] + m*v[i]; ll = max(ll, t1), rr = min(rr, t2); } if (ll <= rr) { ans = m; r = m; } else l = m; } printf("%.12lf/n", ans); return 0;}新闻热点
疑难解答
