题目描述
作为学校违纪行为的代言人，小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 ，表示答案。
解析
贪心的思路比较好找，对于每个\(a _ i\)，找到序列中第一个大等于\(a_i + k\)的位置，则该位置以及该位置之后的数都可以与\(a_i\)进行配对，因为贪心，我们选择\(a _ i\) 和第一个位置配对，但这样有一个错误例子：序列为1， 2， 3， 4， 5， 6。 k = 2时，1与3配对，2与4配对，这样只能配成两对，更优的方式是1-4，2- 5,3 - 6.
序列中最多可以分成n/2对，所以我们将序列对半砍，规定前一半只能和后一半中的数配对，这样就避免了上面的错误情况，用指针维护求ans的过程。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int n, k, a[N];
signed main() {
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> a[i];
int ans = 0;
int r = ((n + 1) >> 1) + 1;//对半砍
for (int i = 1; i <= ((n + 1) >> 1); i ++) {
while (r <= n && a[r] - a[i] < k) r ++;
if (r <= n) ans ++, r ++;
}
cout << ans << '\n';
return 0;
}
晒完代码晒堂主......
