Chương trình C++ kiểm tra có sắp xếp mảng để công thức cho m không

Cho mảng A kích thước n và số m. Kiểm tra có sắp xếp A sao cho sum_{i=1}^n sum_{j=i}^n A[j]/j = m (chia nguyên).

Ví dụ

Với A=[2,5,1], m=8, đầu ra True. Sắp xếp [1,2,5]: (1/1+2/2+5/3)+(2/2+5/3)+(5/3)=8.

Giải thuật

Công thức đơn giản hóa: mỗi A[j] xuất hiện đúng j lần trong tổng kép, mỗi lần chia cho j. Do đó tổng = sum A[j]. Chỉ cần kiểm tra tổng mảng có bằng m không.

Mã C++

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

bool solve(vector<int> A, int m) {
    long sum = 0;
    int n = A.size();
    for (int i = 0; i < n; ++i) sum += A[i];
    return sum == m;
}

int main() {
    vector<int> A = { 2, 5, 1 };
    int m = 8;
    cout << solve(A, m) << endl;
}

Đầu vào / Đầu ra

Input: { 2, 5, 1 }, 8
Output: 1