โค้ด C++ หาผลรวมต่ำสุดของไพ่หลังทิ้ง

สมมติว่าเรามีตัวเลข 5 ตัวในอาร์เรย์ T มีไพ่ 5 ใบ แต่ละใบมีตัวเลข ใบที่ i มี T[i] เราสามารถทิ้งไพ่บางใบได้ เป้าหมายคือลดผลรวมตัวเลขบนไพ่ที่เหลือ อนุญาตให้ทิ้งสูงสุด 1 ครั้ง ไพ่ 2 หรือ 3 ใบที่มีตัวเลขเดียวกัน ไม่ทิ้งถ้าไม่สามารถเลือก 2 หรือ 3 ใบที่มีตัวเลขเดียวกันได้ หาผลรวมต่ำสุด

เช่น ถ้าอินพุตคือ T = [7, 3, 7, 3, 20] เอาต์พุตจะเป็น 26 เพราะทิ้ง 2 ใบที่มีเลข 7 เหลือ 3+3+20 = 26

ขั้นตอนการแก้ปัญหา

n := 5
m := 0
กำหนดอาร์เรย์ k ขนาด 101 เติม 0
for i := 0 ถึง n-1:
    a := T[i]
    m := m + a
    เพิ่ม k[a] ขึ้น 1
M := m
for i := 0 ถึง 100:
    if k[i] > 1:
        M := min(M, m - i * min(3, k[i]))
return M

ตัวอย่างโค้ด

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

int solve(vector<int> T) {
    int n = 5, m = 0, a;
    int k[101] = { 0 };
    for (int i = 0; i < n; i++) {
        int a = T[i];
        m += a;
        k[a]++;
    }
    int M = m;
    for (int i = 0; i < 101; i++)
        if (k[i] > 1)
            M = min(M, m - i * (min(3, k[i])));
    return M;
}

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

อินพุต

{ 7, 3, 7, 3, 20 }