数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：计算参加电影节的观众可以完整观看的电影数量
假设正在举办一个电影节，展映来自不同国家的各种电影。现在，一位参加者希望参加尽可能多的不重叠的电影，我们需要帮助他们找出可以参加的电影数量。
有一个名为Movie的结构体，包含以下成员：
- 电影的开始时间。
- 电影的时长。
- 电影的结束时间。
还有一个名为Festival的结构体，包含以下成员：
- 电影节上电影的数量。
- 一个类型为Movie的数组，其大小与电影节上电影的数量相同。
我们需要创建一个Festival对象，并使用两个数组'timeBegin'和'duration'分别初始化电影的开始时间和时长。整数n表示电影的总数，也用于初始化对象。我们进一步利用该对象来计算参加者可以完整观看的电影数量。
因此，如果输入类似于timeBegin = {1, 3, 0, 5, 5, 8, 8}，duration = {3, 2, 2, 4, 3, 2, 3}，n = 7，则输出将为4。
参加者可以在该电影节上完整观看总共4部电影。
为了解决这个问题，我们将遵循以下步骤：
- struct Movie {
- 定义三个成员变量timeBegin、duration、timeEnd
- 重载运算符‘<’，它将接收一个Movie类型的变量和另一个。
- 返回timeEnd < another.timeEnd
- struct Festival {
- 定义一个成员count
- 定义一个包含Movie类型项的数组movies
- 定义一个函数initialize()。它将接收数组timeBegin和timeEnd以及一个整数n。
- filmFestival := 一个新的Festival对象
- filmFestival的count := count
- 用于初始化 i := 0，当 i < count 时，更新（将i增加1），执行：
- temp := 一个新的Movie类型对象
- temp的timeBegin:= timeBegin[i]
- temp的duration:= duration[i]
- temp的timeEnd := timeBegin[i] + duration[i]
- 将temp插入到filmFestival的数组movies中
- 返回filmFestival
- 定义一个函数solve()，它将接收一个Festival类型的变量fest，
- res := 0
- 对fest的数组movies进行排序
- timeEnd := -1
- 用于初始化 i := 0，当 i < fest - > count 时，更新（将i增加1），执行：
- 如果fest的movies[i]的timeBegin >= timeEnd，则：
- （将res增加1）
- timeEnd := fest的movies[i]的timeEnd
- 如果fest的movies[i]的timeBegin >= timeEnd，则：
- 返回res
示例
让我们看看以下实现以更好地理解：
#include<bits/stdc++.h>
using namespace std;
struct Movie {
int timeBegin, duration, timeEnd;
bool operator<(const Movie& another) const {
return timeEnd < another.timeEnd;
}
};
struct Festival {
int count;
vector<Movie> movies;
};
Festival* initialize(int timeBegin[], int duration[], int count) {
Festival* filmFestival = new Festival;
filmFestival->count = count;
for (int i = 0; i < count; i++) {
Movie temp;
temp.timeBegin = timeBegin[i];
temp.duration = duration[i];
temp.timeEnd = timeBegin[i] + duration[i];
filmFestival->movies.push_back(temp);
}
return filmFestival;
}
int solve(Festival* fest) {
int res = 0;
sort(fest->movies.begin(), fest->movies.end());
int timeEnd = -1;
for (int i = 0; i < fest->count; i++) {
if (fest->movies[i].timeBegin >= timeEnd) {
res++;
timeEnd = fest->movies[i].timeEnd;
}
}
return res;
}
int main(int argc, char *argv[]) {
int timeBegin[] = {1, 3, 0, 5, 5, 8, 8};
int duration[] = {3, 2, 2, 4, 3, 2, 3};
Festival * fest;
fest = initialize(timeBegin,duration, 7);
cout << solve(fest) << endl;
return 0;
}输入
int timeBegin[] = {1, 3, 0, 5, 5, 8, 8};
int duration[] = {3, 2, 2, 4, 3, 2, 3};
Festival * fest;
fest = initialize(timeBegin,duration, 7);输出
4
更新于： 2021年10月20日
372 次浏览
广告