【題目鏈接】:http://codeforces.com/contest/782/PRoblem/B
【題意】 每個(gè)人都有一個(gè)速度,只能往上走或往下走; 然后讓你找一個(gè)地方,所有人都能夠在t時(shí)間內(nèi)到達(dá); 讓t最小.
【題解】 很明顯的二分了; 二分時(shí)間t; 對(duì)于某個(gè)時(shí)間t,這個(gè)人都有一個(gè)能夠到達(dá)的唯一區(qū)間 [x[i]-v*t..x[i]+v*t] 如果所有人的區(qū)間都有交集. 那么就能在那些交集里面隨便選一個(gè)點(diǎn)了; 區(qū)間的交集可以用 最大的左端點(diǎn)小于等于最小的右端點(diǎn)這個(gè)依據(jù)來(lái)判斷是否存在 想讓答案的精度高一點(diǎn),就讓程序的二分多做幾次就好; 固定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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
