C++ – T84893 流星 三分

题目链接:https://www.luogu.org/problem/T84893

众所众知,二分用来查找单调序列中的内容,三分用来查找单峰序列中的内容。

题目

[pdf id=434]

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const long long INF = 0x7fffffff;
const long double EPS = 1e-6;    //控制精度
int n, k;
int ffmax = -INF;   //暴力上限
int ffmin = INF;    //暴力下限
long double ans = INF;
vector > map; //点集
//利用勾股定理,已知直角边,求斜边
long double gc(long double a, long double b) {
	return sqrtl((a * a) + (b * b));
}
//输入流星坐标,求流星到每个恒星之和
long double istrue(long double lx, long double ly) {
	long double ans = 0;
	for(int i = 0; i < map.size(); i++) {
		long double x = map[i].first;
		long double y = map[i].second;
		ans += gc(x - lx, y - ly);
	}
	return ans;
}
//用三分暴力求解,l为下限,r为上限
long double bw(long double l, long double r) {
	if(r - l <= EPS) return l;  //如果l等于r,表示区间中只剩一个答案了
	long double p  = 3.0;
	long double mid1 = l + (r - l) / p;
	long double mid2 = r - (r - l) / p;
	if(istrue(mid1, k) < istrue(mid2, k))  //如果左边小,就把r设置为mid2
		return bw(l, mid2);
	else return bw(mid1, r);     //反之,l设置为mid1
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		map.push_back(make_pair(x, y));
		if(x > ffmax) ffmax = x;
		if(x < ffmin) ffmin = x; 
	}
	scanf("%d", &k);
	//注释部分的代码是打表调试和枚举暴力(会TLE)求解的代码
//	for(int i = ffmin; i <= ffmax; i++) {
//		long double temp = istrue(i, k);
//		if(temp < ans) ans = temp;
//		printf("%d: %.2lf\n", i, temp);
//	}
	ans = istrue(bw(ffmin, ffmax), k);
//	cout<

发表回复