Fork me on GitHub

Codeforces875E

Codeforces875E

题解:

  • 首先二分答案,然后从后往前跑目的地维护可存在的区间。区间不存在或者开始点不在最终区间就不行,否则可以。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 100009
#define mid (l+r>>1)
using namespace std;
int n,s,t,a[N];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
bool check(int x)
{
if (abs(s-t)>x) return 0;
int l=a[n]-x,r=a[n]+x;
for (int i=n-1;i;i--)
{
int L=a[i]-x,R=a[i]+x;
if (a[i]<l||a[i]>r)
{
L=max(L,l);
R=min(R,r);
}
if (L>R) return 0;
l=L,r=R;
}
return (s>=l&&s<=r||t>=l&&t<=r);
}
int main()
{
n=read(),s=read(),t=read();
for (int i=1;i<=n;i++) a[i]=read();
int l=0,r=1000000000,ret=1000000000;
while (l<=r)
{
if (check(mid)) ret=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ret);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces875E

文章作者:wzf2000

发布时间:2017年12月26日 - 10:12

最后更新:2017年12月26日 - 10:12

原始链接:https://wzf2000.github.io/2017/12/26/Codeforces875E/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。