P10126 题解

I_will_AKIOI · 2024-02-04 16:46:26 · 题解

题目给的是一个长度为 n 的序列，太麻烦了，我们把数据规模缩小成 2 个数来思考。

假设这两个数是 2 和 3，得到方程 |3-y|>|2-y|。

若 y\le2：

无解。

若 2<y\le3：

若 y>3：

无解。

所以我们可以求出 y 的范围是 (-\infty,2.5)。

也可以根据绝对值的几何意义，得出 y 一定在他们中点的左侧。

同样的，如果两个数反过来，那么 y 一定在中点右侧。

于是，我们可以一直枚举相邻两个数，求出 y 的范围，不断缩小。枚举完成后，看看左端点是否小于右端点，否则无解。否则输出这个区间的中点。

注意开始两个端点要赋成最值，并且输出时注意保留 10 位小数。我赛时被卡了好几发。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005];
double l=-1e9,r=1e9;
signed main()
{
  ios::sync_with_stdio(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<n;i++)
  {
    if(a[i]<=a[i+1]) r=min(r,0.5*(a[i]+a[i+1]));
    if(a[i]>=a[i+1]) l=max(l,0.5*(a[i]+a[i+1]));
    //不写if-else的原因是防止两数相等
  }
  if(l>=r) cout<<"pigeon";
  else printf("lovely\n%.10f",0.5*(l+r));
  return 0;
}