বাতিল করার পরে ন্যূনতম কার্ডের যোগফল পেতে C++ কোড

ধরুন আমাদের একটি অ্যারে টি-তে পাঁচটি সংখ্যা আছে। পাঁচটি কার্ড আছে এবং প্রতিটি কার্ডে একটি নম্বর লেখা আছে। ith কার্ডে T[i] লেখা আছে। আমরা কিছু কার্ড বাতিল করতে পারি এবং আমাদের লক্ষ্য হল অবশিষ্ট সংখ্যার উপর লেখা সংখ্যার যোগফল কমিয়ে আনা। তাকে সর্বাধিক একবার একই নম্বর সহ দুটি বা তিনটি কার্ড বাতিল করার অনুমতি দেওয়া হয়। একই নম্বরের সাথে দুটি বা তিনটি কার্ড বেছে নেওয়া অসম্ভব হলে আমরা কার্ডগুলি বাতিল করব না। আমাদের সম্ভাব্য ন্যূনতম যোগফল খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি T =[7, 3, 7, 3, 20] এর মত হয়, তাহলে আউটপুট হবে 26, কারণ 7 নম্বর সহ দুটি কার্ড সরিয়ে ফেললে বাকি যোগফল হবে 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 }