http://codeforces.com/problemset/problem/990/B
这题是sorting+贪心,怪不得TE了惹QAQ
You know that you havenbacteria in the Petri dish and size of thei-th bacteria isai. Also you know intergalactic positive integer constantK
The i-th bacteria can swallow thej-th bacteria if and only ifai>ajandai≤aj+K. Thej-th bacteria disappear, but thei-th bacteria doesn't change its size. The bacteria can perform multiple swallows. On each swallow operation any bacteriaican swallow any bacteriajifai>ajandai≤aj+K. The swallow operations go one after another.
For example, the sequence of bacteria sizes a=[101,53,42,102,101,55,54]and K=1. The one of possible sequences of swallow is:[101,53,42,102,101––––,55,54]→[101,53–––,42,102,55,54]→[101––––,42,102,55,54]→[42,102,55,54–––]→[42,102,55]. In total there are 3 bacteria remained in the Petri dish.
Input
The first line contains two space separated positive integers n and K(1≤n≤2⋅105,1≤K≤106) — number of bacteria and intergalactic constant K
The second line contains space separated integers a1,a2,…,an(1≤ai≤106) — sizes of bacteria you have.
Output
Print the only integer — minimal possible number of bacteria can remain.
example:[20,15,10,15,20–––,25]→[20,15,10,15–––,25]→[20,15,10–––,25]→[20,15–––,25]→[20–––,25]→[25].
以下是正确的（抄来的）代码
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, k, a[200001], i, t = 0, j;
cin >> n >> k;
for (i = 0; i<n; i++)
{
cin >> a[i];
}
sort(a, a + n);
for (i = 0; i<n - 1; i = j)
{
for (j = i + 1; j<n&&a[j] == a[i]; j++);//数字相同的都是会被吞的
if ((a[j] <= a[i] + k) && a[j]>a[i])
{
t = t + j - i;//有多少个被吞
}
}
cout << n - t;//剩下没被吞的
return 0;
}
我还是一脸懵逼，留着先
