मान लीजिए एक निर्माता किसी विशेष उत्पाद के लिए विशिष्ट पार्ट्स बनाता है। निर्माता के पास पार्ट्स की n विभिन्न विविधताएँ हैं, और पार्ट्स की तीन मानदंडों पर विशिष्ट रेटिंग है। n उत्पादों की रेटिंग 'ratings' सरणी में दी गई है जहाँ प्रत्येक तत्व (A, B, C) प्रारूप में है जहाँ A, B, C उत्पाद के विभिन्न रेटिंग मानदंड हैं। अब एक OEM अपने द्वारा बनाए जाने वाले प्रत्येक उत्पाद के लिए निर्माता से m पार्ट्स खरीदना चाहता है। OEM निम्न शर्तों को पूरा करने वाले पार्ट्स चुनता है:
- एक ही पार्ट की दो या अधिक इकाइयाँ नहीं खरीदी जानी चाहिए।
- पार्ट्स का ऐसा सेट चुनें जिससे मान V अधिकतम हो, जहाँ V = |कुल रेटिंग मानदंड A| + |कुल रेटिंग मानदंड B| + |कुल रेटिंग मानदंड C|।
हमें OEM द्वारा चुने गए पार्ट्स से V के अधिकतम संभावित मान की गणना करनी है।
उदाहरण के लिए, यदि इनपुट है n = 6, m = 4, ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}, तो आउटपुट 56 होगा।
यदि OEM पार्ट्स 1, 3, 5, और 6 चुनता है, तो प्रत्येक श्रेणी के लिए कुल रेटिंग हैं:
श्रेणी A = 2 + 4 + 7 + 4 = 17 श्रेणी B = 3 + 8 + 2 + 3 = 16 श्रेणी C = 5 + 5 + 7 + 6 = 23 कुल मान V = 17 + 16 + 23 = 56
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
N := 100
आकार 9×N का सरणी arr परिभाषित करें
एक सरणी ans परिभाषित करें
i := 0 से n-1 तक:
a := ratings[i] का पहला मान
b := ratings[i] का दूसरा मान
c := ratings[i] का तीसरा मान
arr[1][i] := a + b + c
arr[2][i] := a - b - c
arr[3][i] := a + b - c
arr[4][i] := a - b + c
arr[5][i] := -a + b + c
arr[6][i] := -a - b - c
arr[7][i] := -a + b - c
arr[8][i] := -a - b + c
i := 1 से 8 तक:
arr[i] सरणी को सॉर्ट करें
i := 1 से 8 तक:
arr[i] सरणी को उलट दें
यदि m == 0, तो V := 0
अन्यथा:
j := 1 से 8 तक:
k := 0
i := 0 से m-1 तक:
k := k + arr[j][i]
V := max(V, k)
V लौटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; const int modval = (int) 1e9 + 7; #define N 100 int solve(int n, int m, vector<tuple<int, int, int>> ratings) { int V, arr[9][N] ; vector<int> ans ; for(int i = 0 ; i < n ; i++) { int a, b, c; tie(a, b, c) = ratings[i]; arr[1][i] = a + b + c ; arr[2][i] = a - b - c ; arr[3][i] = a + b - c ; arr[4][i] = a - b + c ; arr[5][i] = -a + b + c ; arr[6][i] = -a - b - c ; arr[7][i] = -a + b - c ; arr[8][i] = -a - b + c ; } for(int i = 1 ; i <= 8 ; i++) sort(arr[i] , arr[i] + n) ; for(int i = 1 ; i <= 8 ; i++) reverse(arr[i] , arr[i] + n) ; if (m == 0) V = 0 ; else { for (int j = 1; j <= 8; j++) { int k = 0; for (int i = 0; i < m; i++) k += arr[j][i]; V = max(V, k); } } return V; } int main() { int n = 6, m = 4; vector<tuple<int, int, int>> ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}; cout<< solve(n, m, ratings); return 0; }
इनपुट
6, 4, {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3,6}}
आउटपुट
56
