Đếm số phép toán giảm số K về âm theo mảng vòng C++

Cho số nguyên dương K và mảng Ops[] chứa các số nguyên. Thực hiện các phép toán tuần tự để giảm K xuống < 0:

1. Phép 1: K = K + Ops[0]
2. Phép i: K = K + Ops[i] (i duyệt vòng tròn 0..N-1)

Dừng khi K < 0. Đếm số phép toán. Nếu không thể giảm K về âm, trả về -1.

Ví dụ minh họa

Ví dụ 1:

• Input: ops = {-4, 2, -3, 0, 2}, K = 5
• Output: 3
• Giải thích: 5+(-4)=1, 1+2=3, 3+(-3)=0 (chưa <0), tiếp tục... Thực tế output 3 nghĩa là sau 3 phép K≤0.

Ví dụ 2 (Không thể giảm):

• Input: ops = {5, 5, 3, -2}, K = 10
• Output: -1 (K cannot be reduced)
• Giải thích: Tổng mảng = 11 > 0. Mỗi chu kỳ K tăng thêm 11, không bao giờ âm.

Quan sát quan trọng

Nếu sum(Ops) ≥ 0, thì sau mỗi chu kỳ đầy đủ K không giảm (thậm chí tăng). Do đó K không bao giờ < 0. Trả về -1 ngay lập tức.

Mã nguồn C++

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

long countOperations(int op[], int n, int k) {
    long count = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) sum += op[i];
    
    if (sum >= 0) return -1;  // K không bao giờ giảm được
    
    while (k > 0) {
        for (int i = 0; i < n; i++) {
            if (k > 0) {
                count++;
                k += op[i];
            } else {
                break;
            }
        }
    }
    return count;
}

int main() {
    int Ops[] = {1, -1, 5, -11};
    int len = sizeof(Ops) / sizeof(Ops[0]);
    int K = 10;
    long ans = countOperations(Ops, len, K);
    if (ans == -1) cout << "K khong the giam!!";
    else cout << "So phep toan: " << ans;
    return 0;
}

Kết quả chạy chương trình

So phep toan: 8

Độ phức tạp

• Thời gian: O(K / |sum| × n) - có thể lớn nếu K lớn và sum gần 0.
• Không gian: O(1).

Tối ưu hóa O(n) - Toán học

Tính số chu kỳ đầy đủ có thể thực hiện trước khi K ≤ 0:

long countOperationsOptimized(int op[], int n, long long k) {
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += op[i];
    if (sum >= 0) return -1;
    
    // Tính prefix sums
    vector prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + op[i];
    
    // Số chu kỳ đầy đủ
    long long fullCycles = (k - 1) / (-sum);  // Số chu kỳ để K vẫn > 0
    k += fullCycles * sum;
    long long count = fullCycles * n;
    
    // Xử lý phần dư
    for (int i = 0; i < n && k > 0; i++) {
        count++;
        k += op[i];
    }
    return count;
}