最小化要在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