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
    • 返回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 次浏览

开启您的 职业生涯

完成课程并获得认证

立即开始
广告