HƯỚNG DẪN GIẢI BÀI TOÁN: ĐẢO NGƯỢC VÒNG TRÒN TỪ VỊ TRÍ K (DNVT.CPP)

1. Phân tích bài toán

• Yêu cầu: Cho một dãy gồm ~n~ số nguyên và một chỉ số vị trí ~k~. Cần in ra các phần tử theo thứ tự đếm lùi bắt đầu từ vị trí ~k~. Khi lùi qua vị trí đầu tiên (vị trí 1), dãy sẽ tự động vòng lại từ vị trí cuối cùng (vị trí ~n~) và tiếp tục lùi cho đến khi in đủ ~n~ phần tử.
• Ví dụ phân tích:
  • Dãy: 1 2 3 4 5 6 7 8 9 10 với ~n = 10, k = 6~.
  • Bắt đầu lùi từ vị trí ~k = 6~:
    • Đoạn 1 (từ ~k~ về 1): 6 5 4 3 2 1.
    • Đoạn 2 (vòng về cuối từ ~n~ về ~k+1~): 10 9 8 7.
  • Kết quả ghép lại: 6 5 4 3 2 1 10 9 8 7.
• Giới hạn dữ liệu:
  • ~1 \le n \le 10^5~.
  • Giá trị các phần tử có trị tuyệt đối không vượt quá ~10^9~ (dùng mảng kiểu int hoặc long long).
  • ~1 \le k \le n~.
• Cấu trúc dữ liệu: Mảng 1 chiều lưu tối thiểu ~10^5 + 5~ phần tử.

2. Ý tưởng & Thuật toán

Để giải quyết bài toán đếm lùi vòng tròn, ta có thể chia làm 2 vòng lặp đơn giản:

1. Vòng lặp 1: Duyệt ngược từ chỉ số ~i = k~ giảm dần về ~1~, in ra các phần tử ~a[i]~.
2. Vòng lặp 2: Tiếp tục duyệt ngược từ chỉ số ~i = n~ giảm dần về ~k + 1~, in ra các phần tử ~a[i]~. (Nếu ~k = n~, vòng lặp thứ 2 sẽ tự động không thực hiện, logic vẫn hoàn toàn chính xác).

3. Mã nguồn C++ (DNVT.CPP)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int a[MAXN];

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Nhập mảng 1 chiều với chỉ số từ 1 đến n
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int k;
    cin >> k;

    // Đoạn 1: Lùi từ vị trí k về 1
    for (int i = k; i >= 1; i--) {
        cout << a[i] << " ";
    }

    // Đoạn 2: Lùi vòng tròn từ cuối dãy (n) về k + 1
    for (int i = n; i >= k + 1; i--) {
        cout << a[i] << " ";
    }

    cout << "\n";

    return 0;
}

4. Đánh giá độ phức tạp

• Độ phức tạp thời gian (Time Complexity): ~\mathcal{O}(n)~. Chúng ta duyệt qua dãy 1 lần để nhập và 1 lần để in đúng ~n~ phần tử, thời gian thực thi khoảng ~0.01 - 0.02~ giây, chạy rất nhanh và an toàn trong thời gian 1 giây.
• Độ phức tạp không gian (Space Complexity): ~\mathcal{O}(n)~ do chỉ sử dụng mảng 1 chiều tĩnh kích thước ~10^5~ số nguyên (chiếm chưa tới 1 MB bộ nhớ).