Rock Valley P5250 [Shamji 17.Example 5] Lumber Warehouse

[SZ 17.Example 5] Timber Warehouse

Title Description

The city of Boai has a lumber warehouse that stores lumber of various lengths, but ensures that no two lumber lengths are the same. As the head of the warehouse, you sometimes stock in and sometimes ship out, and therefore need to maintain this inventory. There are no more than 100000 operations:

• Incoming, Format1 Length: Put a length (not exceeding) in the warehouse.\(10^9\)) of the wood. If there is already wood of the same length then outputAlready Exist。
• Shipping, Format2 Length: Removes a piece of lumber from the warehouse with a length of Length. If there is no timber of exactly the right length, take out the closest timber to the required length that exists in the warehouse. If there are more than one wood that meets the requirement, take out the shorter one. Outputs the length of the removed wood. If the warehouse is empty, outputEmpty。

input format

not have

output format

not have

Sample #1

Sample Input #1

7
1 1
1 5
1 3
2 3
2 3
2 3
2 3

Sample Output #1

3
1
5
Empty

Thoughts:

• In this question we observe that we need to quickly find out if there is a length of lumber in the warehouse, and we also need to get the length of lumber out of the warehouse, with these two properties we would naturally think of set, which is able to retrieve it quickly and can also delete an element of the set quickly.
• First, we define a set, and then loop n operations, if x == 1, we will find, find the output Already Exist, and line feed. Otherwise, we enter the logic of x=2, first determine whether the set is empty, empty we output empty, otherwise we use lower_bound to find the first position greater than or equal to the length of the position
• Let pointer i point to the first ≥length position in set, and let pointer j point to the same position as pointer i first. And determine the two special cases of i:

1. i points to the position of (), at this point assign j to i (just don't move), at this point j is the position we want to delete, and remember to output it before deleting it
2. i points to the position of (), at this point assign j to the position of i-1, which is the position of the last element in set, at this point j is the piece of wood we want to get out of the warehouse
3. If i is somewhere in the middle, we have to determine which position of i-1 is closer to length and which position of i. Because lower_bound can only find the first position ≥ length, it does not directly determine which of the previous position and this position found is closer to the retrieved value, so we first letj--, and then determine the location of the two from the length of who is closer, if i is closer to the length, just re-assign j to i on the line

				else {
					j--;
					if (*i - length < length - *j) j = i;
				}

4. Finally, remember to outputjand remove the element pointed to by j from the set.

cout << *j << endl.
//Here you can write *j, you can also write only j, only j indicates that the position corresponding to the iterator j is deleted, write *j indicates that the element pointed to by j is deleted.
(*j).

Code:

#include<set>
#include<iostream>
using namespace std;
int n;
int x, length;
set<int> s;
int main()
{
	cin >> n;
	while (n--) {
		cin >> x >> length;
		if (x == 1) {
			if ((length) == ()) (length);
			else cout << "Already Exist" << endl;
		}
		else if (x == 2) {
			if (()) cout << "Empty" << endl;
			else {
				auto i = lower_bound((),(), length);
				auto j = i;
				if (i == ()) j = i;
				else if (i == ()) {
					i--; j = i;
				}
				else {
					j--;
					if (*i - length < length - *j) j = i;
				}
				cout << *j << endl;
				(*j);
			}
		}
	}
	return 0;
}