資料結構
網路
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 次瀏覽
廣告