Bình luận

• 
  

  0

  

  deanqkhanh  đã bình luận lúc 29, Tháng 12, 2025, 4:08

  1. Mô tả lại bài toán

  Cho một xâu S độ dài N chỉ gồm hai kí tự < và >.

  Cần xây dựng một dãy số nguyên không âm A gồm N + 1 phần tử sao cho:

  • Nếu S[i] = '<' thì A[i] < A[i+1]
  • Nếu S[i] = '>' thì A[i] > A[i+1]

  Trong tất cả các dãy thỏa mãn điều kiện trên, hãy tìm tổng nhỏ nhất của các phần tử trong dãy A.

  Giới hạn:

  • |S| ≤ 5 * 10^5

  ---

  2. Nhận xét quan trọng

  • Mỗi dấu < hoặc > chỉ tạo ra ràng buộc giữa hai phần tử kề nhau.
  • Để tổng nhỏ nhất, mỗi phần tử A[i] nên được gán giá trị nhỏ nhất có thể nhưng vẫn thỏa tất cả các ràng buộc.

  • Một vị trí i có thể đồng thời bị ép:

    • tăng dần từ bên trái (do các dấu <)
    • giảm dần từ bên phải (do các dấu >)

  Do đó, cần xét ảnh hưởng từ cả hai phía.

  ---

  3. Xử lý ràng buộc từ trái sang phải

  Xây dựng mảng L với ý nghĩa:

  L[i] = giá trị nhỏ nhất mà A[i] bắt buộc phải đạt được nếu chỉ xét các dấu < ở bên trái.

  Cách xây dựng:

  • L[0] = 0

  • Với mỗi i từ 0 đến N-1:

    • Nếu S[i] = '<' thì L[i+1] = L[i] + 1
    • Nếu S[i] = '>' thì L[i+1] = 0

  Lý do:

  • Chuỗi các dấu < liên tiếp buộc dãy A phải tăng dần từng bước tối thiểu là 1.
  • Khi gặp >, ràng buộc tăng từ trái bị ngắt.

  ---

  4. Xử lý ràng buộc từ phải sang trái

  Xây dựng mảng R với ý nghĩa:

  R[i] = giá trị nhỏ nhất mà A[i] bắt buộc phải đạt được nếu chỉ xét các dấu > ở bên phải.

  Cách xây dựng:

  • R[N] = 0

  • Với mỗi i từ N-1 xuống 0:

    • Nếu S[i] = '>' thì R[i] = R[i+1] + 1
    • Nếu S[i] = '<' thì R[i] = 0

  Lý do:

  • Chuỗi các dấu > liên tiếp buộc dãy A phải giảm dần, nên từ phải qua trái ta phải tăng dần giá trị tối thiểu.

  ---

  5. Ghép hai phía để có nghiệm tối ưu

  Tại mỗi vị trí i, để thỏa đồng thời cả hai phía:

  • Phải có A[i] ≥ L[i]
  • Phải có A[i] ≥ R[i]

  Do đó:

  A[i] = max(L[i], R[i])
  

  Giá trị này là:

  • đủ để thỏa mọi ràng buộc
  • nhỏ nhất có thể
  • nếu giảm thêm sẽ vi phạm điều kiện
  • nếu tăng thêm thì làm tổng lớn hơn, không tối ưu

  Tổng nhỏ nhất cần tìm là:

  ans = sum(max(L[i], R[i])) với i = 0..N
  

  ---

  6. Độ phức tạp

  • Thời gian: O(N)
  • Bộ nhớ: O(N)
  • Phù hợp với giới hạn bài toán

  ---

  7. Cài đặt C++

  #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  
  int main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
  
      string S;
      cin >> S;
      int N = S.size();
  
      vector<ll> L(N + 1, 0), R(N + 1, 0);
  
      // Xử lý từ trái sang phải
      for (int i = 0; i < N; i++) {
          if (S[i] == '<') L[i + 1] = L[i] + 1;
          else L[i + 1] = 0;
      }
  
      // Xử lý từ phải sang trái
      for (int i = N - 1; i >= 0; i--) {
          if (S[i] == '>') R[i] = R[i + 1] + 1;
          else R[i] = 0;
      }
  
      ll ans = 0;
      for (int i = 0; i <= N; i++) {
          ans += max(L[i], R[i]);
      }
  
      cout << ans << '\n';
      return 0;
  }
  

  ---

  8. Kết luận

  Bài toán được giải bằng tư duy:

  • tách ràng buộc thành hai phía độc lập
  • mỗi phía cho ra một giá trị tối thiểu bắt buộc
  • nghiệm tối ưu đạt được khi mỗi phần tử bằng ràng buộc mạnh nhất tác động lên nó

  Đây là một bài tham lam chuẩn, thường xuất hiện trong các contest về dãy và bất đẳng thức.