ধরুন, একটি কোম্পানিতে এন কর্মচারী আছে। কর্মচারীদের প্রত্যেককে তাদের দক্ষতার ভিত্তিতে একটি পদ দেওয়া হয়। র্যাঙ্কগুলি 1 থেকে k পর্যন্ত সংখ্যা করা হয়েছে। একটি র্যাঙ্ক i আছে এমন কর্মচারীর সংখ্যা অ্যারে দক্ষতায় দেওয়া হয়, যেখানে দক্ষতা[i] র্যাঙ্ক i প্রাপ্ত কর্মচারীর সংখ্যাকে প্রতিনিধিত্ব করে। এখন, কোম্পানির একটি নতুন শাখা খোলা হয়েছে এবং বিভিন্ন দক্ষতার কর্মচারীদের সেই শাখায় পরিবহন করতে হবে। ওই শাখায় পাঠানো কর্মচারীর সংখ্যা মি. আমাদের একটি উপায় খুঁজে বের করতে হবে যাতে আমরা বিভিন্ন দক্ষতা সম্পন্ন কর্মচারীদের সেই নতুন শাখায় স্থানান্তর করতে পারি। শাখার কর্মচারী পদ বরাদ্দ টেবিল শাখা পেতে আমাদের নিম্নলিখিত সূত্রটি ছোট করতে হবে।
সূত্র হল:max(শাখা[i]/m - দক্ষতা[i]/n).
শাখার মানের সমষ্টি [i] ফলে m হয়। আমাদের শাখা[i] এর উপাদানগুলি খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট হয় k =5, n =10, m =25, দক্ষতা ={5, 3, 2, 7, 4}, তাহলে আউটপুট হবে 12 7 5 17 10।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
sum := 0
for initialize i := 0, when i < k, update (increase i by 1), do:
skill[i] := skill[i] * m / n
Define an array a containing integer pairs
for initialize i := 0, when i < k, update (increase i by 1), do:
c := skill[i]
sum := sum + c
first value of a[i] := skill[i] - c
second value of a[i] := i
sort the array a
reverse the array a
for initialize i := 0, when i < m - sum, update (increase i by 1), do:
skill[second value of a[i]] := skill[second value of a[i]] + 1
for initialize i := 0, when i < k, update (increase i by 1), do:
if i is not equal to k - 1, then:
print(skill[i])
Otherwise,
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
