Đếm số phép toán biến đổi mảng A thành B bằng C++

Mô tả bài toán

Hai mảng A,B cùng kích thước n. Phép toán: chọn i,j, giảm A[i] 1, tăng A[j] 1 (phần tử không âm). Tìm dãy phép toán biến A thành B. Không thể thì -1.

Ví dụ

A=[1,2,3,4], B=[3,1,2,4] → (1,0), (2,0) (giảm chỉ số 1,2 tăng chỉ số 0).

Thuật toán

Kiểm tra tổng A == tổng B. Tính C[i]=A[i]-B[i]. Tổng |C[i]| / 2 là số phép. Lặp: tìm i với C[i]>0 (dư), j với C[j]<0 (thiếu), thực hiện phép (i,j), cập nhật C.

Code C++

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

void solve(vector A, vector B) {
    int n = A.size();
    long long sumA = 0, sumB = 0;
    for (int x : A) sumA += x;
    for (int x : B) sumB += x;
    if (sumA != sumB) {
        cout << -1;
        return;
    }
    vector C(n);
    int ops = 0;
    for (int i = 0; i < n; i++) {
        C[i] = A[i] - B[i];
        ops += abs(C[i]);
    }
    ops /= 2;
    int i = 0, j = 0;
    while (ops--) {
        while (C[i] <= 0) i++;
        while (C[j] >= 0) j++;
        cout << "(" << i << ", " << j << "), ";
        C[i]--; C[j]++;
    }
}

int main() {
    vector A = {1,2,3,4};
    vector B = {3,1,2,4};
    solve(A, B);
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2,3,4}, {3,1,2,4}

Output: (1, 0), (2, 0),