欢迎来到CooooldWind_的试炼历程
本系列主要是讲自己在平常做题的时候的一些小花絮，但是已经托更很久了，趁着刚搞好GitHub Pages，今天把之前的都推下（外传就算了吧）。
想法
想法很简单，这不就是个栈？
但是有个点注意下，行和行建立待处理数组和栈的时候为什么用long long类型而不是朴实无华的int?
因为最大元素大小，我怕超了（
完整答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
long long nums[10000];
int n,c;
int main(){
cin >> n >> c;
for(int i = 0;i < n;i++) cin >> nums[i];
int output = 0;
stack<long long> s;
int pos = 0;
while(s.size() + output < n){
int zone_lost = c - s.size();
int min_pos;
long long minn = 2*10*10*10*10*10*10*10*10*10;
for(int r = pos;r < min(pos + zone_lost,n);r++){
if(nums[r] < minn){
minn = nums[r];
min_pos = r;
}
}
long long min_num = nums[min_pos];
if(s.empty() || s.top() > min_num){
for(int i = pos;i <= min_pos;i++) s.push(nums[i]);
pos = min(min_pos + 1,n - 1);
}
cout << s.top() << " ";
s.pop();
output++;
}
while(s.empty() == 0) {
cout << s.top() << " ";
s.pop();
}
}
|
讲解
定义和输入
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<bits/stdc++.h>
using namespace std;
long long nums[10000];
int n,c;
int main(){
cin >> n >> c;
for(int i = 0;i < n;i++) cin >> nums[i];
int output = 0;
stack<long long> s;
int pos = 0;
|
就这里，和对应题目里面的和，是第二行的输入，计算经过处理的数字量，指目前计算的位置。
while循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| while(s.size() + output < n){
int zone_lost = c - s.size();
int min_pos;
long long minn = 2*1000000000;
for(int r = pos;r < min(pos + zone_lost,n);r++){
if(nums[r] < minn){
minn = nums[r];
min_pos = r;
}
}
long long min_num = nums[min_pos];
if(s.empty() || s.top() > min_num){
for(int i = pos;i <= min_pos;i++) s.push(nums[i]);
pos = min(min_pos + 1,n - 1);
}
cout << s.top() << " ";
s.pop();
output++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
里面的第一个for循环寻找待处理数组中前```zone_lost```位中最小的位置（就是能存进去的里面找最小的那个在哪）。
如果```pos+zone_lost```超了数组最大值的话那就不好了，所以为了检测它超了还是没超，得有```min(pos + zone_lost,n)```在for的判断里面出现。
底下的if就是一个个存到$s$，直到存到刚刚说的“能存进去的里面找最小的那个”的位置。
if底下的三行依次是输出、出栈、累加。
#### 底下的while循环
```cpp
while(s.empty() == 0) {
cout << s.top() << " ";
s.pop();
}
|
因为有时候栈不可能在数组里面的数处理完的时候完全空，所以写了while循环。
自此这题就解完啦。
看起来不难，但其实还是有点深度。
这个题解非常蒟蒻向，大佬们别喷。
蒟蒻写的题解有人点赞嘛？
