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
广告