攀
爬
攀爬
攀爬
正
解
部
分
\color{red}{正解部分}
正解部分
若存在一个合法的攀爬序列, 则其形式一定是
a
k
+
∑
i
=
1
m
(
a
i
−
b
i
)
≥
L
a_{k} + \sum\limits_{i=1}^m (a_i - b_i) \geq L
ak+i=1∑m(ai−bi)≥L, 于是考虑枚举
a
k
a_k
ak, 设
d
i
=
a
i
−
b
i
d_i = a_i-b_i
di=ai−bi, 按
d
d
d 从大到小 排序, 然后
O
(
N
)
O(N)
O(N) 解出 爬出井 的最早时间, 更新答案, 总时间复杂度
O
(
N
2
)
O(N^2)
O(N2) .
考虑怎么优化, 记
s
u
m
i
=
∑
j
=
1
i
d
j
sum_i = \sum\limits_{j=1}^i d_j
sumi=j=1∑idj, 设最早被淹死的时间为
d
a
y
day
day,
d
a
y
=
min
(
i
∣
s
u
m
i
≤
∑
j
=
1
i
c
j
)
day = \min(i\ |\ sum_i \le \sum\limits_{j=1}^i c_j)
day=min(i ∣ sumi≤j=1∑icj), 只需要在
s
u
m
i
,
i
∈
[
1
,
d
a
y
]
sum_i, i ∈ [1, day]
sumi,i∈[1,day] 中 二分查找
L
−
a
k
L - a_k
L−ak 即可得到 关于
a
k
a_k
ak 的答案,
但是随着
a
k
a_k
ak 的变化,
s
u
m
i
sum_i
sumi 同样也在变化, 我们要使得这种变化更加 “平滑”, 更加易于控制一点,
于是我们将
a
k
a_k
ak 从右往左 枚举, 考虑取出
a
k
a_k
ak 会对哪些
s
u
m
i
sum_i
sumi 造成影响, 会对
s
u
m
p
,
p
∈
[
k
,
n
]
sum_p, p ∈ [k, n]
sump,p∈[k,n] 造成影响, 这种变化会使得
s
u
m
p
′
=
s
u
m
p
+
d
i
+
1
−
d
k
sum^{'}_p = sum_p + d_{i+1} - d_k
sump′=sump+di+1−dk,
由于
d
k
d_k
dk 从右向左 枚举, 且
{
d
i
}
\{d_i\}
{di} 是 递减的, 所以
d
k
d_k
dk 是不断增大的, 进而
s
u
m
p
′
sum^{'}_p
sump′ 是不断减少的, 所以
d
a
y
day
day 只有可能不断向左移动, 而向左移动最多移动
N
N
N 步, 所以按上述方法暴力移动
d
a
y
day
day, 总复杂度是
O
(
N
log
N
)
O(N \log N)
O(NlogN) 的 .
但是这里要提到的是, 当出现
d
i
<
0
d_i < 0
di<0 的情况时,
s
u
m
i
{sum_i}
sumi 并非单调, 为了应对这种情况, 需要找出一个中准点
m
d
md
md, 使得
[
1
,
m
d
]
[1, md]
[1,md] 是单调递增的, 在
[
1
,
min
(
d
a
y
,
m
d
)
]
[1, \min(day, md)]
[1,min(day,md)] 中 二分查找 即可 .
实
现
部
分
\color{red}{实现部分}
实现部分
注意一步就能跳到井口的情况需要特判 .
#include<bits/stdc++.h>
#define reg register
typedef long long ll
;
int read(){
char c
;
int s
= 0, flag
= 1;
while((c
=getchar()) && !isdigit(c
))
if(c
== '-'){ flag
= -1, c
= getchar(); break ; }
while(isdigit(c
)) s
= s
*10 + c
-'0', c
= getchar();
return s
* flag
;
}
const int maxn
= 100005;
int N
;
int L
;
ll C
[maxn
];
ll sum
[maxn
];
struct Pill
{ int a
, b
, d
; } A
[maxn
];
bool cmp(Pill x
, Pill y
){ return x
.d
> y
.d
; }
int lower_bound(int l
, int r
, const int &aim
, const int &k
){
int res
= -1;
while(l
<= r
){
int mid
= l
+r
>> 1;
ll tmp
= sum
[mid
] + ((mid
>=k
)?(-A
[k
].d
+A
[mid
+1].d
):0);
(tmp
>= aim
) ? r
= mid
- 1, res
= mid
: l
= mid
+ 1;
}
return res
;
}
int main(){
N
= read(), L
= read();
for(reg
int i
= 1; i
<= N
; i
++) A
[i
].a
= read(), A
[i
].b
= read(), A
[i
].d
= A
[i
].a
- A
[i
].b
;
std
::sort(A
+1, A
+N
+1, cmp
);
for(reg
int i
= 1; i
<= N
; i
++) C
[i
] = C
[i
-1] + read();
int day
= N
;
for(reg
int i
= 1; i
<= N
; i
++){
sum
[i
] = sum
[i
-1] + A
[i
].d
;
if(sum
[i
] <= C
[i
]) day
= std
::min(day
, i
);
if(sum
[i
] < sum
[i
-1] && (i
-1)) day
= std
::min(day
, i
);
}
int Ans
= -1;
for(reg
int k
= N
; k
>= 1; k
--){
if(day
>= k
){
ll d
= sum
[day
] - A
[k
].d
+ A
[day
+1].d
;
while(day
>= k
&& d
<= C
[day
]) day
--, d
= sum
[day
]-A
[k
].d
+A
[day
+1].d
;
}
int pos
= lower_bound(1, day
, L
-A
[k
].a
, k
);
if(pos
!= -1){ if(Ans
== -1) Ans
= pos
; else Ans
= std
::min(Ans
, pos
); }
}
if(Ans
!= -1) Ans
++;
if(Ans
== 2) Ans
--;
printf("%d\n", Ans
);
return 0;
}
