Untitled
unknown
plain_text
18 days ago
1.0 kB
3
Indexable
Never
#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