Advertisement
DimaT1

Untitled

Mar 2nd, 2018
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. typedef long long ll;
  6.  
  7. struct x {
  8.     ll coord; // координата
  9.     ll p;     // предок (по умолчанию -1)
  10.     ll vc;    // мин кол-во великов
  11. };
  12.  
  13. int main() {
  14.     ll n, k;
  15.     std::cin >> n >> k;
  16.     std::vector<x> xs(n);
  17.  
  18.     for (ll i = 0; i < n; i++) {
  19.         std::cin >> xs[i].coord;
  20.         xs[i].p = -1;
  21.         xs[i].vc = -1;
  22.     }
  23.     xs[0].p = 0;
  24.     xs[0].vc = 0;
  25.  
  26.     for (ll i = 0; i < n; i++) {
  27.         if (xs[i].p != -1) {
  28.             for (ll j = i + 1; (j < n) and (xs[i].coord + k >= xs[j].coord); j++) {
  29.                 if (xs[j].p == -1 or xs[j].vc > xs[i].vc + 1) {
  30.                     xs[j].p = i;
  31.                     xs[j].vc = xs[i].vc + 1;
  32.                 }
  33.             }
  34.         }
  35.     }
  36.  
  37.     std::cout << xs[n-1].vc << std::endl;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement