[Codeforces] 782B. The Meeting Place Cannot Be Changed

題目連結:http://codeforces.com/problemset/problem/782/B
其實本題是對答案二分搜,驗證方法是當你把時間乘上速率後可以得到每個人最遠走到哪,看有沒有交集就知道解是否合法,不過本題有更無腦的方式,那就是對集合點模擬退火(其實是因為我當時看一眼就想到這個做法就沒去想正解了XD
#include <bits/stdc++.h>
using namespace std;
#define N 60000

double pos[N+5], speed[N+5];
int n;

inline double getY(double x);

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%lf",&pos[i]);
	for(int i=0;i<n;i++)scanf("%lf",&speed[i]);
	double rr=*max_element(pos,pos+n);
	double ll=*min_element(pos,pos+n);
	default_random_engine rEng(time(NULL));
	uniform_real_distribution<double> Range(-1,1);
	uniform_real_distribution<double> expR(0,1);
	auto Random=bind(Range,rEng);
	auto expRand=bind(expR,rEng);
	int step=0;
	double pace=rr-ll, mini=0.95;
	double x=max(min(Random()*pace+ll, rr), ll), y=getY(x);
	while(pace>=1e-7){
		double newX = max(min(x + Random()*pace, rr), ll);
		double newY = getY(newX);
		if(newY < y || expRand() < exp(-step))
			x=newX, y=newY;
		step++;
		pace*=mini;
	}
	printf("%.9lf", y);
	return 0;
}

inline double getY(double x){
	double ans=-2147483647;
	for(int i=0;i<n;i++)
		ans = max(ans, abs(x-pos[i])/speed[i]);
	return ans;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology