数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告