Fork me on GitHub

Uoj#357.【JOI2017春季合宿】Sparklers

Uoj#357.【JOI2017春季合宿】Sparklers 题解

题意:

  • 简单来说就是$n$个人跑来跑去,保持烟火不灭所需要的最小速度。
  • $1\le n\le 10^5,0\le x_i\le 10^9$。

题解:

  • 首先可以想到二分答案。
  • 然后就是一个判定性问题。
  • 我们设$s$为一次传递最多跑的距离。
  • 显然每个时刻点燃过烟火的人可以是一段区间。
  • 如果$[l,r-1]$或者$[l,r+1]$可行区间非空,那么$[l,r]$时传递给的人的可行区间就是$[x_r-(r-l)\times s,x_l+(r-l)\times s]$。(如果区间不存在就是不可行)
  • 可行也就是$x_r-x_l\le 2\times (r-l)\times s$。
  • 设$a_i=x_i-2\times i\times s$,那么$a_r\le a_l$,将每个人抽象为$(i,a_i)$。
  • 那么就是要求一种从$(K,K)$变换到$(1,n)$的方案,使得每一时刻都有左边点在右边上方。
  • 可以分情况讨论一下:
    • 如果有一种只往左走的方法可以使左侧变高,走过去显然不会比现在差。(右侧同理)
    • 如果两边都不存在变高的方法,那么设当前左侧为$l$,设$l$左侧最低的点为$x$,$x$左侧(包含$x$)最高的点为$y$,那么如果从$l$走到$x$,必然连续地走到$y$。右侧同理。
    • 这时我们发现在这种情况下,左边不可能变高,右边不可能变低。
    • 所以在两侧都可行的情况下,选择顺序是对结果没有影响的。
    • 区间最大最小都可以通过$\rm ST$表实现。
  • 复杂度$O(n\log n\log Ans)$。

代码:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 100009
#define mid (l+r>>1)
using namespace std;
int n,K,T,a[N],pre[N],nxt[N],lg[N],bit[20],q[N],top,Min[20][N],Max[20][N];
ll A[N];
int read()
{
char ch;
int x=1;
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;
}
int get_min(int l,int r)
{
if (l>r) return 0;
int k=lg[r-l+1];
if (A[Min[k][l]]<A[Min[k][r-bit[k]+1]]) return Min[k][l];
else return Min[k][r-bit[k]+1];
}
int get_max(int l,int r)
{
if (l>r) return 0;
int k=lg[r-l+1];
if (A[Max[k][l]]>A[Max[k][r-bit[k]+1]]) return Max[k][l];
else return Max[k][r-bit[k]+1];
}
bool check(int v)
{
int s=v*T;
for (int i=1;i<=n;i++) A[i]=a[i]-2ll*i*s,Min[0][i]=Max[0][i]=i;
for (int i=1;i<20;i++)
for (int j=1;j+bit[i]-1<=n;j++)
{
if (A[Min[i-1][j]]<A[Min[i-1][j+bit[i-1]]]) Min[i][j]=Min[i-1][j];
else Min[i][j]=Min[i-1][j+bit[i-1]];
if (A[Max[i-1][j]]>A[Max[i-1][j+bit[i-1]]]) Max[i][j]=Max[i-1][j];
else Max[i][j]=Max[i-1][j+bit[i-1]];
}
top=0;
for (int i=1;i<=n;pre[i]=q[top],q[++top]=i,i++)
while (top&&A[q[top]]<=A[i]) top--;
top=0;
for (int i=n;i;nxt[i]=q[top],q[++top]=i,i--)
while (top&&A[q[top]]>=A[i]) top--;
int L=K,R=K;
while (L>1||R<n)
{
if (pre[L]&&A[get_min(pre[L],L-1)]>=A[R]) L=pre[L];
else if (nxt[R]&&A[get_max(R+1,nxt[R])]<=A[L]) R=nxt[R];
else
{
int x=get_min(1,L-1),y=get_max(R+1,n);
if (L==1) return A[y]<=A[L];
if (R==n) return A[x]>=A[R];
if (A[x]<A[R]||A[y]>A[L]) return 0;
int xx=get_max(1,x),yy=get_min(y,n);
if (A[xx]>=A[y]) L=xx;
else if (A[yy]<=A[x]) R=yy;
else return 0;
}
}
return 1;
}
int main()
{
bit[0]=1;
for (int i=1;i<20;i++) bit[i]=bit[i-1]<<1;
lg[0]=-1;
for (int i=1;i<N;i++) lg[i]=lg[i>>1]+1;
n=read(),K=read(),T=read();
for (int i=1;i<=n;i++) a[i]=read();
int l=0,r=1000000000/T+1,ret=0;
while (l<=r)
{
if (check(mid)) ret=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ret);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#357.【JOI2017春季合宿】Sparklers

文章作者:wzf2000

发布时间:2018年03月14日 - 15:03

最后更新:2018年03月14日 - 18:03

原始链接:https://wzf2000.github.io/2018/03/14/Uoj357/

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