P5250 木材仓库

萌新的第一篇题解

题意就是往一个仓库里放不同长度的木材。

然后维护这个仓库。

这里其实定义一个Set然后对它进行维护就好了。

关于Set这里不详细展开讲了，请自行百度了解。

AC代码如下，思路在注释里

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <set>
 4 using namespace std;
 5 set<int>s;//描述仓库
 6 set<int>::iterator it, it2;//定义两个迭代器用来描述位置
 7 int main() {
 8     int n = 0;
 9     scanf("%d", &n);
10     while (n--) {
11         int a, b;
12         scanf("%d%d", &a, &b);
13         if (a == 1) {
14             if (s.find(b) != s.end()) {
15                 printf("Already Exist\n");
16             }
17             else {
18                 s.insert(b);
19             }
20         }
21         if(a == 2){//注意需要一些特判
22             if (s.size() == 0) {
23                 printf("Empty\n");
24                 continue;
25             }
26             if (s.size() == 1) {//如果只有一个则只能拿出这一个
27                 it = lower_bound(s.begin(), s.end(), 0);
28                 printf("%d\n", *it);
29                 s.erase(*it);//erase()//取出
30                 continue;
31             }
32             if (s.find(b) != s.end()) {//如果已经有这个长度的木材就将其取出
33                 printf("%d\n", b);
34                 s.erase(b);
35                 continue;
36             }
37             else {//如果没有这个长度的木材
38                 it = lower_bound(s.begin(), s.end(), b);//找到第一个大于被取数的木头在哪里
39                 if (it == s.begin()) {//如果这个木头位于set首位，说明已经没有比被取数更小的木头，直接输出这个木头
40                     printf("%d\n", *it);
41                     s.erase(*it);
42                     continue;
43                 }
44                 if (it == s.end()) {//如果没有找到比被取数大的木头，则输出set最尾端的木头长度，即"it--"处的木头
45                     it--;
46                     printf("%d\n", *it);
47                     s.erase(*it);
48                     continue;
49                 }
50                 else{//如果被取数左右都有木头，
51                     it2 = it;//it2保存大的那个
52                     it--;//it保存小的那个
53                     if (b - *it > *it2 - b) {//比较他们与被取数之间的差，输出差值较小的那个，若一样，输出小的那个
54                         printf("%d\n", *it2);
55                         s.erase(*it2);
56                         continue;
57                     }
58                     if (b - *it <= *it2 - b) {
59                         printf("%d\n", *it);
60                         s.erase(*it);
61                         continue;
62                     }
63                 }
64             }
65         }
66     }
67     //完美结束
68     return 0;
69 }