मान लीजिए, एक कंपनी में n कर्मचारी हैं। प्रत्येक कर्मचारी को उनके कौशल के आधार पर एक रैंक दी गई है। रैंक 1 से k तक गिनी जाती हैं। रैंक i वाले कर्मचारियों की संख्या ऐरे skill में दी गई है, जहां skill[i] रैंक i वाले कर्मचारियों की संख्या दर्शाता है। अब, कंपनी की एक नई शाखा खुली है और विभिन्न कौशल के कर्मचारियों को उस शाखा में स्थानांतरित किया जाना है। उस शाखा में भेजे जाने वाले कर्मचारियों की संख्या m है। हमें एक ऐसा तरीका ढूंढना है जिससे हम उस नई शाखा में m कर्मचारियों को विभिन्न कौशल के साथ स्थानांतरित कर सकें। हमें निम्नलिखित सूत्र को न्यूनतम करना है ताकि शाखा की कर्मचारी रैंक आवंटन तालिका branch प्राप्त हो सके।
सूत्र है: max(branch[i]/m - skill[i]/n)।
branch[i] के मानों का योग m होता है। हमें branch[i] में तत्वों को ढूंढना है।
उदाहरण के लिए, यदि इनपुट k = 5, n = 10, m = 25, skill = {5, 3, 2, 7, 4} है, तो आउटपुट 12 7 5 17 10 होगा।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
sum := 0 i := 0 से k-1 तक, करें: skill[i] := skill[i] * m / n पूर्णांक युग्मों वाला एक ऐरे a परिभाषित करें i := 0 से k-1 तक, करें: c := skill[i] sum := sum + c a[i] का पहला मान := skill[i] - c a[i] का दूसरा मान := i ऐरे a को सॉर्ट करें ऐरे a को उलट दें i := 0 से m - sum - 1 तक, करें: skill[a[i] का दूसरा मान] := skill[a[i] का दूसरा मान] + 1 i := 0 से k-1 तक, करें: यदि i, k - 1 के बराबर नहीं है, तो: print(skill[i]) अन्यथा, print(skill[i])
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; void solve(int k, int n, int m, vector<double> skill){ int sum = 0; for (int i = 0; i < k; i++) skill[i] = skill[i] * m / n; vector<pair<double, int>> a(k); for (int i = 0; i < k; i++) { int c = skill[i]; sum += c; a[i].first = skill[i] - c; a[i].second = i; } sort(a.begin(), a.end()); reverse(a.begin(), a.end()); for (int i = 0; i < m - sum; i++) { skill[a[i].second] += 1; } for (int i = 0; i < k; i++) { if (i != k - 1) cout << int(skill[i]) << " "; else cout << int(skill[i]) << endl; } } int main() { int k = 5, n = 10, m = 25; vector<double> skill = {5, 3, 2, 7, 4}; solve(k, n, m, skill); return 0; } इनपुट
5, 10, 25, {5, 3, 2, 7, 4} आउटपुट
12 7 5 17 10
