5208: [AHOI2018初中组]报名签到
[Creator : ]
Description
$n$ 位同学(编号从 $1$ 到 $n$)同时来到体育馆报名签到,领取准考证和参赛资料。
为了有序报名,这 $n$ 位同学需要按编号次序(编号为 $1$ 的同学站在最前面)从前往后排成一条直线。然而每一位同学都不喜欢拥挤,对于第 $i$ 位同学,如果有另外一位同学距离他(她)的距离小于 $a_i$,那么就会发生冲突。
小周周想知道如果要不发生任何冲突的情况下,这 $n$ 位同学排队的队列最短长度是多少。
为了有序报名,这 $n$ 位同学需要按编号次序(编号为 $1$ 的同学站在最前面)从前往后排成一条直线。然而每一位同学都不喜欢拥挤,对于第 $i$ 位同学,如果有另外一位同学距离他(她)的距离小于 $a_i$,那么就会发生冲突。
小周周想知道如果要不发生任何冲突的情况下,这 $n$ 位同学排队的队列最短长度是多少。
Input
输入有两行:
第一行一个整数 $n$,表示报名签到的同学人数。
第二行有 $n$ 个整数,第 $i$ 个整数 $a_i$ 表示第 $i$ 个同学必须与其他同学保持的距离。
第一行一个整数 $n$,表示报名签到的同学人数。
第二行有 $n$ 个整数,第 $i$ 个整数 $a_i$ 表示第 $i$ 个同学必须与其他同学保持的距离。
Output
输出一行,包括一个整数,表示这 $n$ 位同学排队队列的最小长度。
注意:$n$ 位同学要按 $1$~$n$ 的次序从前往后排队。
注意:$n$ 位同学要按 $1$~$n$ 的次序从前往后排队。
Constraints
对于 $20\%$ 的数据满足:$1 ≤ n ≤ 20$;
对于 $70\%$ 的数据满足:$1 ≤ n ≤ 10000$;
对于 $100\%$ 的数据满足:$1 ≤ n ≤ 100000,\ 1 ≤ a_i ≤ 100000$。
对于 $70\%$ 的数据满足:$1 ≤ n ≤ 10000$;
对于 $100\%$ 的数据满足:$1 ≤ n ≤ 100000,\ 1 ≤ a_i ≤ 100000$。
Sample 1 Input
4
3 1 2 4
Sample 1 Output
9