Description of the problem:
You have a movie rental company and n movie stores. You want to implement a movie rental system that supports querying, booking and returning movies. A report of the currently loaned movie can also be generated.
All movies are represented by a two-dimensional integer array entries, where entries[i] = [shopi, moviei, pricei] indicates that the store shopI has a copy of the movie movieI at the rental price of pricei. Each store has at most one copy of the movie numbered moviei.
The system needs to support the following operations:
Search: Find the cheapest five stores that have the specified movies and have not been lent. Shops need to be sorted in ascending order by price, and smaller shopi stores come first if prices are the same. If the query results are less than 5 stores, return them all. If the query results do not have any stores, an empty list is returned.
Rent: Loan a specified movie from a specified store with a title that guarantees that the specified movie is not loaned at the specified store.
Drop: The specified movie that has been lent before it is returned by the designated store.
Report: Return the cheapest five loaned movies (which may have duplicate movie ID s) and return the results with a two-dimensional list res, where res[j] = [shopj, moviej] indicates that the jth cheapest loaned movie is moviej, which was loaned from the store shopj. Movies in res need to be sorted in ascending order by price; Shopj smaller ranks first if prices are the same; If it's still the same, moviej Smaller comes first. If fewer than five movies are currently loaned, return them all. If no movies are currently being loaned, an empty list is returned.
Please implement the MovieRentingSystem class:
The MovieRentingSystem (int n, vector<vector<int>>& entries) initializes the MovieRentingSystem object with a list of movies represented by N stores and entries.
Vector<int> search(int movie) returns the list of stores that did not lend the specified movie as described above.
* void rent(int shop, int movie) borrows the specified movie from the specified store shop shop.
(void drop(int shop, int movie) movie lent before the specified store shop returns it.
Vector<vector<int> report() Returns the cheapest list of five loaned movies, as described above.
Note: The test data guarantees that the specified store in the rent operation owns the specified movie that was not loaned and that the specified store in the drop operation has loaned the specified movie before.
Example 1:
Input:
3 6
0 1 5
0 2 6
0 3 7
1 1 4
1 2 7
2 1 5
search 1
rent 0 1
rent 1 2
report
drop 1 2
search 2
Output:
1 0 2
0 1
1 2
0 1
Explanation:
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1); //Return [1, 0, 2] (output a line in the results), Store 1, 0 and 2 have movies with an unloaded ID of 1. Shop 1 is the cheapest and stores 0 and 2 have the same price, so they are sorted by store number.
MovieRentingSystem. Rent(0,1); // Loan Movie 1 from store 0. Store 0 is not currently lending a movie number of [2,3].
MovieRentingSystem. Rent(1,2); // Loan Movie 2 from Shop 1. Store 1's unloaded movie number is now [1].
movieRentingSystem.report(); //Returns [[0, 1], [1, 2] (two rows output in the result). Store 0 borrowed the cheapest movie 1, followed by Store 1 borrowed movie 2.
movieRentingSystem.drop(1, 2); // Return Movie 2 at Store 1. Store 1's unloaded movie number is now [1,2].
movieRentingSystem.search(2); //Returns [0, 1] (one line is output in the result). Store 0 and 1 have movies with an unloaded ID of 2. Shop 0 is cheapest, then Shop 1.
Input description:
Enter several lines:
The first row contains two integers, N and m, n representing the number of movie stores, and M representing the number of rows in the entries array used to initialize the object.
Then m lines, each with three integers shopi, moviei, pricei representing each line of entries.
There are several subsequent lines, each of which is entered as one of search, rent, drop, or report:
If the directive is of search type, you need to enter an integer after it to represent the movie.
If the instruction is of type rent, you need to enter two integers after it to represent show and movie.
If the instruction is of type drop, two integers need to be entered after it to represent shop and movie.
If the instruction is of type report, no integer is required later.
Tips:
1 <= n <= 3 * 10^5
1 <= m <= 10^5
0 <= shopi < n
1 <= moviei, pricei <= 10^4
At most one copy of the movie moviei is available in each store.
The total number of calls to search, rent, drop, and report is no more than 10^5.
Output description:
Output several lines:
The return value of the search or report directive for each behavior.
The array returned by the search directive, each integer being output followed by a space.
A two-dimensional array returned by the report directive, with multiple lines of output, each output integer followed by a space.
Core idea: Two-structured objects contain pointers to each other, one-to-many and many-to-one correspondence.
Movie_Store contains a Movie* type vector that stores a pointer to the movie it owns;
Movie contains Movie_Store* type of pointer, which represents the pointer of the movie store to which it belongs, and uses ms_number refers to the serial number of the movie store to which it belongs, making it easy to find and reducing one pointer call.
#include <bits/stdc++.h>
using namespace std;
struct Movie;
struct Movie_Store;
struct Movie
{
int data;
int value;
Movie_Store *ms;
int ms_number;
bool rent_if = false;
};
struct Movie_Store
{
int flag;
vector<Movie *> M;
};
vector<Movie_Store> MS;
bool cmp1(Movie a, Movie b)
{
if (a.value != b.value)
{
return a.value < b.value;
}
else
{
return a.ms_number < b.ms_number;
}
}
void Search(int find_data)
{
int len = MS.size();
vector<Movie> result;
for (int i = 0; i < len; i++)
{
int len_m = MS[i].M.size();
for (int j = 0; j < len_m; j++)
{
if (MS[i].M[j]->data == find_data && MS[i].M[j]->rent_if == false)
{
result.push_back(*MS[i].M[j]);
}
}
}
sort(result.begin(), result.begin() + result.size(), cmp1);
int len_result = result.size();
if (len_result > 5)
{
len_result = 5;
}
bool f = false;
for (int i = 0; i < len_result; i++)
{
cout << result[i].ms_number << " ";
}
cout << endl;
}
void Rent(int s, int m)
{
int result_ms;
int len = MS.size();
for(int i=0;i<len;i++)
{
if(MS[i].flag == s)
{
result_ms = i;
}
}
int len_m = MS[result_ms].M.size();
for (int i = 0; i < len_m; i++)
{
if (MS[result_ms].M[i]->data == m)
{
MS[result_ms].M[i]->rent_if = true;
break;
}
}
}
void Drop(int s, int m)
{
int result_ms;
int len = MS.size();
for(int i=0;i<len;i++)
{
if(MS[i].flag == s)
{
result_ms = i;
}
}
int len_m = MS[result_ms].M.size();
for (int i = 0; i < len_m; i++)
{
if (MS[result_ms].M[i]->data == m)
{
MS[result_ms].M[i]->rent_if = false;
break;
}
}
}
bool cmp2(Movie a, Movie b)
{
if (a.value != b.value)
{
return a.value < b.value;
}
else if (a.ms_number != b.ms_number)
{
return a.ms_number < b.ms_number;
}
else
{
return a.data < b.data;
}
}
void Report()
{
int len = MS.size();
vector<Movie> result;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < MS[i].M.size(); j++)
{
if (MS[i].M[j]->rent_if == true)
{
result.push_back(*MS[i].M[j]);
}
}
}
sort(result.begin(), result.begin() + result.size(), cmp2);
int len_result = result.size();
if (len_result > 5)
{
len_result = 5;
}
for (int i = 0; i < len_result; i++)
{
cout << result[i].ms_number << " " << result[i].data << " " << endl;
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
Movie *movie = new Movie;
cin >> movie->ms_number;
cin >> movie->data;
cin >> movie->value;
int len = MS.size();
int f = -1;
for (int j = 0; j < len; j++)
{
if (movie->ms_number == MS[j].flag)
{
f = j;
break;
}
}
if (f != -1)
{
movie->ms = MS.data() + f;
MS[f].M.push_back(movie);
}
else
{
Movie_Store *ms0 = new Movie_Store;
ms0->flag = movie->ms_number;
ms0->M.push_back(movie);
movie->ms = ms0;
MS.push_back(*ms0);
ms0 = NULL;
}
movie = NULL;
}
string str;
while (cin >> str)
{
if (str == "search")
{
int p;
cin >> p;
Search(p);
}
else if (str == "rent")
{
int p, q;
cin >> p >> q;
Rent(p, q);
}
else if (str == "drop")
{
int p, q;
cin >> p >> q;
Drop(p, q);
}
else
{
Report();
}
}
return 0;
}Again: This code is also called "I'm not targeting anyone, I mean, I'm all the mothers present", "TLE Title that will eventually die before 80,000 test cases after a night's demorning's closing."
If you do not change the algorithm, the current teammate gives the optimization idea is 1. Use scanf input to reduce input time by 2. Sort by insertion instead of sort 3. Try whether the hash table is alive
If you have the best ideas, please comment that I can continue to bald. gif