首页 > 代码库 > codeforces 782B - The Meeting Place Cannot Be Changed
codeforces 782B - The Meeting Place Cannot Be Changed
题意：
一条线上有n个人，每个人一个坐标值xi，每个人有一个最大行走速度vi，问如果要让这n个人走到线上某一个点，最少需要多少时间。
分析：
看起来是二分，
二分坐标。
二分区间变化的条件，一开始感觉是比较当前mid坐标左右人们用最快速度到达的平均时间，
后来具体写的时候感觉是比较当前mid坐标左右人们用最快速度到达的最大时间。
其实就是后者。
如果某一边的最大时间比较大的话，坐标就要向那一边偏移，
最后循环退出的条件就是在误差以内。
代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <bitset> 9 #include <string>10 #include <cctype>11 #include <cstdio>12 #include <cstring>13 #include <cstdlib>14 #include <iostream>15 #include <algorithm>16 #include <unordered_map>17 18 using namespace std;19 20 typedef long long ll;21 typedef unsigned long long ull;22 #define inf (0x3f3f3f3f)23 #define lnf (0x3f3f3f3f3f3f3f3f)24 #define eps (1e-6)25 int sgn(double a) {26 return a < -eps ? -1 : a < eps ? 0 : 1;27 }28 29 //--------------------------30 31 const ll mod = 1000000007;32 const int maxn = 100010;33 34 35 struct friends {36 int a, b;37 } f[60010];38 39 bool cmp(friends a, friends b) {40 if(a.a != b.a) return a.a < b.a;41 else return a.b < b.b;42 }43 44 void solve() {45 int n;46 scanf("%d", &n);47 for(int i = 0; i < n; i++) {48 scanf("%d", &f[i].a);49 }50 for(int i = 0; i < n; i++) {51 scanf("%d", &f[i].b);52 }53 sort(f, f + n, cmp);54 double left = f[0].a, right = f[n - 1].a;55 56 while(fabs(right - left) >= 1e-6) {57 double mid = (left + right) / 2;58 double lmax = 0, rmax = 0;59 double maxtime = 0;60 for(int i = 0; i < n; i++) {61 if(f[i].a < mid) {62 lmax = max(lmax, fabs(mid - (double)f[i].a) / f[i].b);63 } else {64 rmax = max(rmax, fabs(mid - (double)f[i].a) / f[i].b);65 }66 maxtime = max(maxtime, fabs(mid - (double)f[i].a) / f[i].b);67 }68 if(lmax < rmax) {69 left = mid;70 } else {71 right = mid;72 }73 }74 double res = fabs(left + right) / 2;75 double ans = 0;76 for(int i = 0; i < n; i++) {77 ans = max(ans, fabs(res - (double)f[i].a) / f[i].b);78 }79 printf("%f\n", ans);80 }81 82 int main() {83 84 #ifndef ONLINE_JUDGE85 freopen("1.in", "r", stdin);86 //freopen("1.out", "w", stdout);87 #endif88 // iostream::sync_with_stdio(false);89 solve();90 return 0;91 }
codeforces 782B - The Meeting Place Cannot Be Changed
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。