最小化要在C ++中分发的泰迪总数
问题陈述
给定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