C++で配布されるテディの総数を最小限に抑えます

問題の説明

N人の学生と、学生が取得したマークを表す配列が与えられます。学校は彼らに価格としてテディを与えるために殺害しました。しかし、学校はお金を節約したいので、次の制約を課すことによって、配布されるテディの総数を最小限に抑えます-

• すべての生徒は少なくとも1つのテディを取得する必要があります
• 2人の生徒が隣り合って座っている場合、点数の高い生徒はもっと多くの生徒を獲得する必要があります
• 2人の生徒が同じ点数を持っている場合、異なる数のテディを取得できます

例

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