समस्या कथन
छात्रों की N संख्या और एक सरणी दी गई है जो छात्रों द्वारा प्राप्त अंक का प्रतिनिधित्व करती है। स्कूल ने उन्हें कीमत के तौर पर टेडी देने का फैसला किया है। होवर, स्कूल पैसे बचाना चाहता है, इसलिए वे निम्नलिखित बाधाओं को लागू करके वितरित किए जाने वाले टेडी की कुल संख्या को कम करने के लिए -
- सभी छात्रों को कम से कम एक टेडी अवश्य मिलना चाहिए
- यदि दो छात्र एक दूसरे के बगल में बैठे हैं तो उच्च अंक वाले छात्र को अधिक अंक प्राप्त करने होंगे
- यदि दो छात्रों के अंक समान हैं तो उन्हें अलग-अलग संख्या में टेडी प्राप्त करने की अनुमति है
उदाहरण
मान लीजिए कि 3 छात्र हैं और प्राप्त अंकों को -
. के रूप में सरणी में दर्शाया गया हैarr[] = {2, 3, 3}
So, total number of teddies to be distributed:
{1, 2, 1} i.e. 4 teddies एल्गोरिदम
डायनेमिक प्रोग्रामिंग का उपयोग करके इस समस्या को हल किया जा सकता है -
1. Create a table of size N and initialize it with 1 as each student must get atleast one teddy 2. Iterate over marks array and perform below step: a. If current student has more marks than previous student then: i. Get the number of teddies given to the previous student ii. Increment teddie count by 1 b. If current student has lesser marks than previous student then: i. Review and change all the values assigned earlier
उदाहरण
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int teddieDistribution(int *marks, int n) {
int table[n];
fill(table, table + n, 1);
for (int i = 0; i < n - 1; ++i) {
if (marks[i + 1] > marks[i]) {
table[i + 1] = table[i] + 1;
} else if (marks[i] > marks[i + 1]) {
int temp = i;
while (true) {
if (temp >= 0 && (marks[temp] >
marks[temp + 1])) {
if (table[temp] >
table[temp + 1]) {
--temp;
continue;
} else {
table[temp] =
table[temp + 1] + 1;
--temp;
}
} else {
break;
}
}
}
}
int totalTeddies = 0;
for (int i = 0; i < n; ++i) {
totalTeddies += table[i];
}
return totalTeddies;
}
int main() {
int marks[] = {2, 6, 5, 2, 3, 7};
int totalTeddies = teddieDistribution(marks,
SIZE(marks));
cout << "Total teddies to be distributed: " <<
totalTeddies << "\n";
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Total teddies to be distributed: 12