資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最小化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
更新於: 2019年10月22日
79 次瀏覽
廣告