P10126 「Daily OI Round 3」Pigeon

题目背景

最近，忙吗，也不说打个电话。哦，是吗，嘿嘿原来没给过你号码。但这，不是，你不找我的理由，下次罚你陪我等到太阳出头。——recollect_i 的博客

题目描述

recollect_i 给了你长度为 $n$ 的序列 $x$，你需要求出一个实数 $y$ 使得对于所有 $1\le i<j\le n$，$|x_j-y|>|x_i-y|$，或报告无解。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数 $x$，表示序列。

输出格式

如果有解，第一行输出字符串 lovely，第二行输出一个实数 $y$。

为了避免精度问题，如果您输出的方案满足对于所有 $ 1\leq i<j\leq n$，$\vert x_j-y\vert-\vert x_i-y\vert>10^{-6}$，则认为您的答案正确。

同时您需要保证 $-2\times 10^9\le y\le 2\times 10^9$，且 $y$ 的小数点后不超过 $10$ 位，否则无法保证评测的正确性。

如果无解，一行输出字符串 pigeon。

输入输出样例 #1

输入 #1

5
1 2 3 4 5

输出 #1

lovely
-114514

输入输出样例 #2

输入 #2

5
3 2 1 6 7

输出 #2

lovely
3.1416

输入输出样例 #3

输入 #3

5
3 2 1 4 5

输出 #3

pigeon

说明/提示

【提示】

输出格式中 $>10^{-6}$ 只是为了避免精度问题，您可以当成要求 $|x_j-y|>|x_i-y|$。

可以证明，如果有解，则一定存在 $y$ 满足 $-2\times 10^9\le y\le 2\times 10^9$ 且对于所有 $1\le i<j\le n$，$|x_j-y|-|x_i-y|>0.2$，且小数点后位数不超过 $3$。

【数据范围】

对于全部数据保证：$5\le n\le 10^5$，$-10^9\le x_i\le 10^9$。

C++实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
const double eps = 1e-6;	//精度
int n;
int a[N];
double l = -2e9 , r = 2e9;	//l和r都是小数，用double存
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i=1 ; i<=n ; i++)	{
		cin >> a[i];
	}
	for (int i=2 ; i<=n ; i++)	{
		if (l>=r || r-l<=eps || a[i]==a[i-1]){
			cout << "pigeon" << endl;
			return 0;
		}
		if (a[i-1]>a[i])	{
			double mid = (double)(a[i-1]+a[i])/2;
			l = max(mid , l);
		}
		if (a[i-1]<a[i])		{
			double mid = (double)(a[i-1]+a[i])/2;
			r = min(mid , r);
		}
	}
	if (l>=r || r-l<eps)	{
		cout << "pigeon" << endl;
		return 0;
	}
	cout << "lovely\n";		//别忘记输出这个了
	cout << fixed << setprecision(7) << l+eps << endl;
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容