破棄後にカードの最小合計を取得するC++コード

配列Tに5つの数字があるとします。5枚のカードがあり、各カードには数字が書かれています。 i番目のカードにはT[i]が書かれています。いくつかのカードを捨てることができます。私たちの目標は、残りの数字に書かれている数字の合計を最小限に抑えることです。彼は多くても同じ番号のカードを2枚か3枚捨てることができます。同じ番号のカードを2枚か3枚選ぶことができない場合、カードを捨てることはありません。可能な限り最小の合計を見つける必要があります。

したがって、入力がT =[7、3、7、3、20]の場合、番号7の2枚のカードを削除すると、出力は26になります。残りの合計は3 + 3 + 20=26になります。

ステップ

これを解決するには、次の手順に従います-

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

例

理解を深めるために、次の実装を見てみましょう-

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

出力

26