मान लीजिए हमारे पास एक सरणी T में पांच संख्याएं हैं। पांच कार्ड हैं और प्रत्येक कार्ड पर एक संख्या लिखी है। iवें कार्ड पर 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
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(vector 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 T = { 7, 3, 7, 3, 20 }; cout << solve(T) << endl; }
इनपुट
{ 7, 3, 7, 3, 20 }आउटपुट
26
