AcWing 4483. 格斗场

一个格斗场内有 n 个战士，其中第 i 个战士的战斗力为 ai。

一个长度为n的数组，第i个数的值为ai

作为格斗场内的经理人，你需要给战士们安排一对一的决斗。

从该数组中挑2个数出来；

这些决斗是一场接一场进行的，一场结束后才会安排下一场。

要保证先从数组中挑2个数出来，处理完了这2个数，才能继续挑下一个“2个数”；

为了保证决斗的观赏性，在安排时需保证：
1 决斗双方的战斗力不能相同。

挑的2个数字不能相等，ai != aj， 即 aj - ai >= 1

2 决斗双方的战斗力差距不能超过 K。

2个数字差的绝对值要满足 小于等于K：abs(ai - aj) <= K

已知，在决斗中战斗力高的选手一定可以将战斗力低的选手击败，并且失败的选手会被赶出格斗场。

if (ai > aj) aj被赶出，ai留下

请你合理安排决斗，使得当剩余选手之间无法再安排任何决斗时，剩余选手的数量越少越好。

要使得剩余的选手数量越少越好，那就是 离开的选手数量越多越好。如果按照上面的规则挑选，那么挑出来的2个数字既不相同，又相差不能大于K，那剩下的选手不能安排任何决斗时，一定是剩下的数字要么相同，要么相差太大。

所以可以先把数组进行排序，然后双指针遍历，能决斗的就决斗，小的走，大的留，minv = num.size() - 1;

7 1 [ n = 7, k = 1]
101 53 42 102 101 55 54
sort后:
42 53 54 55 101 101 102

贪心是算法思想，双指针是工具

请你输出剩余选手的最小可能数量minv。

代码中的a[j-1] - a[i] >= 1干了2件事：

(1) i和j-1不能相同，相同的话，a[i]就是a[j-1]，同一个元素，怎么删除呢。
(2) 为了满足题目限制，挑的2个数字不能相同，所以if (a[j-1] != a[i]) res --;也可以。

#include<bits/stdc++.h>
using namespace std;

int n, k;
const int N = 2e5+10;
int a[N];

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);// 42 53 54 55 101 101 102 
    
    int res = n;// n - t : t是可能要删掉的数字
    for (int i = 0, j = 0; i < n; i++)
    {
        while (j < n && a[j] - a[i] <= k) j++;
        // 跳出while循环后，此时的 a[j] 是满足 a[j] - a[i] > k 的，则a[j-1]是满足a[j-1] - a[i] <= k的
        if (i != j-1 && a[j-1] - a[i] >= 1) res --; // 判断 2个数 是否相等, 如果不相等，就删掉a[i], n(res)-1;
    }
    
    cout << res;
    return 0;
}