Bình luận

• 
  

  11

  SPyofgame    3:00 p.m. 8 Tháng 6, 2020 ← chỉnh sửa 24 →

  ---

  Spoiler Alert

  ---

  Hint 1

  Xét một bài toán con: Cho mảng a[] gồm n phần tử. Tìm đoạn con a[l]..a[r] thỏa a[l] + k ≥ a[r]

  ---

  Hint 2

  Xài two-pointer, ta dễ dàng giải quyết vấn đề trên với độ phức tạp nhỏ hơn

  ---

  Reference bài toán con | \(O(n)\) time | \(O(1)\) auxiliary space | Two-pointers

  C++

  int n = readInt();
  vector<int> a(n);
  for (int &x : a) cin >> x;
  
  int max_size = 0;
  for (int l = 0, r = 0; l < n; ++l) /// O(n)
  {
      while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
      int cur_size = r - l + 1;
      max_size = max(max_size , cur_size);
  }
  cout << max_size ;
  

  Hint 3

  Xét bài toán đề yêu cầu. Với các bài toán con có n - 1 phần tử, ta tính toán.

  Kết quả sẽ là result = min{ giá trị các bài toán con }

  Ngoài việc thử tạo từng mảng con mà bị loại đi phần tử p. Ta có thể duyệt p qua và thực hiện swap(a[0], a[p + 1]) thì a[1]..a[n - 1] là một mảng con mới đã loại phần tử p + 1. Từ đó giảm độ phức tạp không gian

  ---

  Reference thuật trâu | 50 điểm + TLE | \(O(n ^ 2)\) time | \(O(1)\) auxiliary space | Brute-forces, Two-pointers

  C++

  int n = readInt();
  vector<int> a(n);
  for (int &x : a) cin >> x;
  
  int result = n;
  for (int p = 0; p + 1 < n; swap(a[0], a[p + 1]), ++p) /// O(n ^ 2)
  {
      int max_size = 0;
      for (int l = 0, r = 0; l < n; ++l) /// O(n)
      {
          while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
          int cur_size = r - l + 1;
          max_size = max(max_size, cur_size);
          if (max_size > result) break; /// Can
      }
      result = min(result, max_size);
  }
  cout << result;
  

  Hint 4

  Để bỏ vòng lặp ngoài, ta có nhận xét như sau: Ta chỉ cần tìm 2 đoạn con dài nhất ai..aj thỏa ai + k ≥ aj

  Gọi độ dài đoạn dài nhất là max_size1, độ dài đoạn dài nhì là max_size2, ta có:

  Xét 2 trường hợp

  • max_size1 ≠ max_size2 thì result = max_size1 - 1

    (loại bỏ đi một phần tử)

  • max_size1 = max_size2 thì result = max_size1

    (loại bỏ đi một phần tử của đoạn dài max_size1, nhưng vẫn còn đoạn dài max_size2 = max_size1)

  ---

  Reference Thuật tham lam | 81 điểm + WA | \(O(n)\) time | \(O(1)\) auxiliary space | Greedy, Two-pointers

  C++

  int n = readInt();
  vector<int> a(n);
  for (int &x : a) cin >> x;
  
  int max_size1 = 0, max_size2 = 0;
  for (int l = 0, r = 0; l < n; ++l) /// O(n)
  {
      while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
      int cur_size = r - l + 1;
  
           if (cur_size > max_size1) max_size2 = max_size1, max_size1 = cur_size;
      else if (cur_size > max_size2) max_size2 = cur_size;
  }
  cout << max_size1 - (max_size2 != max_size1);
  

  Hint 5

  Spot lỗi sai trong thuật trên nào: Đó là chưa xét trường hợp khi 2 đoạn con lồng vào nhau, dẫn tới việc khi xóa một phần tử chung của 2 đoạn con max_size1, max_size2 thì độ dài 2 đoạn con còn lại max_size1 - 1, max_size2 - 1 => res = max_size1 - 1

  Để sửa vấn đề này. Ta thêm 2 biến là:

  • pos_1 lưu vị trí cuối cùng của đoạn con đầu tiên dài max_size1

  • pos_2 lưu vị trí đầu tiên của đoạn con cuối cùng dài max_size2

  Xét các trường hợp

  • (max_size1 ≠ max_size2) thì result = max_size1 - 1

    (loại bỏ đi một phần tử)

  • (max_size1 = max_size2) và (pos_2 <= pos_1) thì result = max_size1 - 1

    (loại bỏ đi một phần tử chung của 2 đoạn con max_size1, max_size2)

  • (max_size1 = max_size2) và (pos_2 > pos_1) thì result = max_size1

    (loại bỏ đi một phần tử của đoạn con max_size1 nhưng vẫn còn đoạn con max_size2)

  ---

  Reference Thuật Two-pointer | 100 điểm = AC | \(O(n)\) time | \(O(1)\) query | O(1) auxiliary space | Online Solving, Two-pointers

  C++

  int n = readInt();
  vector<int> a(n);
  for (int &x : a) cin >> x;
  
  int max_size1 = 0, max_size2 = 0;
  int  pos_1 = 0,  pos_2 = 0;
      for (int l = 0, r = 0; l < n; ++l) /// O(n)
      {
          while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
          int cur_size = r - l + 1;
  
           if (cur_size == max_size1) pos_2 = l, max_size2 = cur_size;
      else if (cur_size  > max_size1) pos_1 = r, max_size1 = cur_size;
  }
  cout << max_size1 - ((max_size1 != max_size2) || ((max_size1 == max_size2) && (pos_2 <= pos_1)));
  

• 
  

  8

  cuom1999    12:38 a.m. 9 Tháng 6, 2020

  Cảm ơn bạn. Đã thêm vào phần lời giải
2 bình luận nữa