B. 【GENOIP#39】小S排座位
1 s
256 MB
题目描述
作为学校违纪行为的代言人，小S被老师安排去排一个新班级的座位。新班级有 $n$ 位同学，他们的成绩按顺序分别为 $a_1,a_2,\dots,a_n$ （ $a_i\leq a_{i+1}$ ）。教室的一桌会坐相邻的两个人，称为同桌。为促进互帮互助，一对同桌的成绩之差的绝对值必须大于等于给定的常数 $K$ ，但这样会导致一些同学没有同桌，而没有同桌的人会去暴D小S。小S不想被D，所以请你求出他最多能排出几对同桌。
输入格式
第一行输入两个整数 $n,K$ ，含义见题目描述。
第二行输入 $n$ 个整数 $a_i$ ，保证数组 $a$ 不降。
输出格式
第一行一个整数 $ans$ ，表示答案。
样例 1
样例 2
数据范围与提示
对于 $100\%$ 的数据，保证 $1\le n\leq 10^6,0\leq a_i,K\leq 10^9$
| 子任务编号 | 分值 | $n\leq$ | $a_i,K\le$ | 特殊性质 |
|---|---|---|---|---|
| $1$ | 5 | $2$ | $10^9$ | 无 |
| $2$ | 15 | $100$ | $10^9$ | 无 |
| $3$ | 15 | $10^6$ | $100$ | 无 |
| $4$ | 15 | $10^6$ | $10^9$ | 保证 $a_i=i$ |
| $5$ | 15 | $10^6$ | $10^9$ | 保证 $K>\dfrac{a_n}{2}$ |
| $6$ | 35 | $10^6$ | $10^9$ | 无 |
OI
Contest Ended