Tìm tổng nhỏ nhất sau khi loại bỏ thẻ bài cùng số bằng C++

Mô tả bài toán

Có 5 thẻ bài số T[0..4]. Có thể loại bỏ một lần 2 hoặc 3 thẻ có cùng số. Mục tiêu: giảm tổng số còn lại đến tối thiểu.

Ví dụ

T = [7,3,7,3,20] → Loại 2 thẻ 7 → còn 3+3+20=26.

Thuật toán

Đếm tần suất mỗi số (1..100). Tổng ban đầu m. Với mỗi số i có tần suất >1, có thể loại min(3, freq[i]) thẻ. Tổng mới = m - i * min(3, freq[i]). Lấy min của các tổng đó.

Code C++

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

int solve(vector<int> T) {
    int n = 5, m = 0;
    int cnt[101] = {0};
    for (int x : T) {
        m += x;
        cnt[x]++;
    }
    int ans = m;
    for (int i = 1; i <= 100; i++) {
        if (cnt[i] > 1) {
            ans = min(ans, m - i * min(3, cnt[i]));
        }
    }
    return ans;
}

int main() {
    vector<int> T = {7,3,7,3,20};
    cout << solve(T) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {7,3,7,3,20}

Output: 26