Untitled
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