Mã C ++ để nhận tổng số thẻ tối thiểu sau khi loại bỏ

Giả sử chúng ta có năm số trong một mảng T. Có năm thẻ và mỗi thẻ có một số được viết trên chúng. Thẻ thứ i có T [i] được viết trên đó. Chúng tôi có thể loại bỏ một số thẻ và mục tiêu của chúng tôi là giảm thiểu tổng số được viết trên các số còn lại. Anh ta được phép bỏ nhiều nhất một lần hai hoặc ba thẻ có cùng số. Chúng tôi sẽ không loại bỏ các thẻ nếu không thể chọn hai hoặc ba thẻ có cùng số. Chúng ta phải tìm ra số tiền tối thiểu có thể.

Vì vậy, nếu đầu vào là T =[7, 3, 7, 3, 20], thì đầu ra sẽ là 26, vì loại bỏ hai thẻ có số 7. Tổng còn lại sẽ là 3 + 3 + 20 =26.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n := 5
m := 0
Define an array k of size: 101 and fill with 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   a := T[i]
   m := m + a
   (increase k[a] by 1)
M := m
for initialize i := 0, when i < 101, update (increase i by 1), do:
   if k[i] > 1, then:
      M := minimum of M and (m - i * (minimum of 3 and k[i]))
return M

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ 7, 3, 7, 3, 20 }

Đầu ra

26