Untitled

mail@pastecode.io avatar
unknown
plain_text
19 days ago
1.1 kB
2
Indexable
Never
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int n, k, tmp, tm, cnt, hieu[100001];
vector<int> v;

int main(){
    // input va sort 
    memset(hieu, 0, 100000);
    cin >> n >> k;
    while(cin >> tmp){
        hieu[tmp] = 1;
        n = max(n, tmp);
    }
    for(int i = 1; i <= n; i++){
        if(hieu[i]) v.push_back(i);
    }
    n = v.size();
    // mang hieu
    hieu[0] = 0; for(int i = 1; i < n; i++) hieu[i] = v[i] - v[i-1];
    
    tm = k*2; tmp = tm; cnt = 0;
    hieu[n] = k+1; // dung de xet phan tu cuoi cung: i = n-1
    for(int i = 1; i <= n; i++){
        tmp -= hieu[i];
        if(tmp < 0 || hieu[i] > k){
            tmp = tm; ++cnt;
        }
        //cout << i << " : " << tmp <<  " : " << hieu[i] << " : " << cnt << endl;
    }
    cout << cnt;
    
    return 0;
}
/*
7 2
9 5 4 2 6 15 12

0 1 2 3 4  5  6 7         !         !        !        !
2 4 5 6 9 12 15 x     2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 2 1 1 3  3  3 5     ^   ^ ^ ^     ^        ^        ^
1 : 2 : 2
2 : 1 : 1
3 : 0 : 1
4 : 4 : 3
5 : 1 : 3
6 : 4 : 3
7 : 4 : 5
3
*/

Leave a Comment