Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
1.0 kB
3
Indexable
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

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

int main(){ // thuat toan dua vao khoang cach
    memset(hieu, 0, 100000);
    cin >> n >> k;
    while(cin >> tmp){
        hieu[tmp] = 1;
        n = max(n, tmp);
    }
    // input
    for(int i = 1; i <= n; i++){
        if(hieu[i]) v.push_back(i);
    }
    tmp = v[0]; n = v.size();
    for(int i = 0; i < n; i++) v[i] -= tmp; 
    // mang hieu
    hieu[0] = 0; for(int i = 1; i < n; i++) hieu[i] = v[i] - v[i-1];
    
    k = k*2; tmp = k; 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){
            tmp = k; ++cnt;
        }
        //cout << i << " : " << tmp <<  " : " << hieu[i] << endl;
    }
    cout << cnt;
    
    return 0;
}
/*
8 2
7 2 4 6 5 9 12 11

0 1 2 3 4 5  6  7 
2 4 5 6 7 9 11 12
0 2 3 4 5 7  9 10

0 1 2 3 4 5  6  7 
0 2 1 1 1 2  2  1
*/






Leave a Comment