Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình C ++ để tìm ra bao nhiêu bộ phim mà một người tham dự có thể xem toàn bộ tại một Liên hoan phim

Giả sử có một liên hoan phim đang diễn ra giới thiệu nhiều bộ phim từ các quốc gia khác nhau. Bây giờ, một người tham dự muốn tham dự số lượng phim tối đa không trùng lặp với nhau và chúng tôi phải giúp họ tìm ra bao nhiêu phim mà họ có thể tham dự.

Có một cấu trúc Phim có các thành viên sau -

  • Thời gian bắt đầu của bộ phim.
  • Thời lượng của phim.
  • Thời gian kết thúc của bộ phim.

Có một Liên hoan cấu trúc khác với các thành viên sau -

  • Số lượng phim tại liên hoan phim.
  • Một loạt các loại Phim có quy mô tương tự với số lượng phim tại liên hoan.

Chúng ta phải tạo và khởi tạo đối tượng Festival với hai mảng 'timeBegin' và 'thời lượng' chứa thời gian bắt đầu và thời lượng của một số phim tương ứng. Một số nguyên n biểu thị tổng số phim và số đó cũng được sử dụng để khởi tạo đối tượng. Chúng tôi còn sử dụng đối tượng đó để tính xem một người tham dự có thể xem đầy đủ bao nhiêu bộ phim.

Vì vậy, nếu đầu vào là timeBegin ={1, 3, 0, 5, 5, 8, 8}, thời lượng ={3, 2, 2, 4, 3, 2, 3}, n =7, thì đầu ra sẽ là 4

Người tham dự có thể xem trọn vẹn 4 bộ phim tại liên hoan phim đó.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • struct Movie {
    • Xác định ba biến thành viên timeBegin, time, timeEnd
    • Quá tải một toán tử ‘<’, điều này sẽ dẫn đến một biến loại Phim khác.
      • return timeEnd
  • struct Festival {
    • Xác định số lượng thành viên
    • Xác định một mảng phim có chứa mục thuộc loại Phim
  • Định nghĩa một hàm khởi tạo (). Điều này sẽ lấy các mảng timeBegin và timeEnd và một vòng lặp n.
    • filmFestival:=Một đối tượng Lễ hội mới
    • số lượng phimFestival:=count
    • để khởi tạo i:=0, khi tôi <đếm, cập nhật (tăng i lên 1), thực hiện -
      • temp:=một đối tượng mới thuộc loại Phim
      • timeBegin of temp:=timeBegin [i]
      • thời lượng tạm thời:=thời lượng [i]
      • timeEnd of temp:=timeBegin [i] + thời lượng [i]
      • chèn tạm thời vào các mảng phim của filmFestival
    • phim trở lại Lễ hội
  • Xác định một hàm giải quyết (), hàm này sẽ sử dụng một biến kiểu Festival,
    • res:=0
    • sắp xếp các mảng phim về lễ hội
    • timeEnd:=-1
    • để khởi tạo i:=0, khi tôi đếm, cập nhật (tăng i lên 1), thực hiện -
      • if timeBegin of movies [i] of fest> =timeEnd, thì -
        • (tăng độ phân giải lên 1)
        • timeEnd:=timeEnd của phim [i] of fest
    • trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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;
}

Đầu vào 

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);

Đầu ra 

4