Description
给一个以空格分隔的字符串, 该字符串只有四种字符, 分别表示:
(1) 空格, 表示分隔符;
(2) 整数, 表示当前插入的值;
(3) 字母 E, 表示从前面已有数字中取走一个最小的值;
(4) 小数点 ".", 表示输入结束;
已知有 n 个插入操作, m 个取走数操作, 求依次取得的 m 个数, 输入保证每次取数时都有数可取. (1≤m≤n≤100000, 每个数字范围在 - 10000 和 10000 之间)
Input
只有一行字符串
Output
只有一行数据, 为 m 个以空格分隔的数, 分别表示依次取得的 m 个最小值.
- Sample Input
- 4 8 E 3 E 10 2 6 E 1.
- Sample Output
- 4 3 2
- HINT
n<=200, 所有输入数据均 <=1000, 所求得的最小值小于 10 的 9 次方.
- Source
- #include<bits/stdc++.h>
- using namespace std;
- int s[100001],len;
- void s_up(int p)
- {
- while(p>1&&s[p/2]>s[p])
- {
- swap(s[p/2],s[p]);
- p=p/2;
- }
- return;
- }
- void s_down(int p)
- {
- int lt;
- while(1)
- {
- if(p*2>len) return;
- if(p*2==len) lt=p*2;
- else
- {
- if(s[p*2]<s[p*2+1])
- lt=p*2;
- else
- lt=p*2+1;
- }
- if(s[p]>s[lt])
- {
- swap(s[p],s[lt]);
- p=lt;
- }
- else break;
- }
- return;
- }
- void insert(int key)
- {
- len++;
- s[len]=key;
- s_up(len);
- }
- int main()
- {
- char c;
- int num=0;
- bool flag=0;
- int fh=1;
- while(1){
- c=getchar();
- if(c=='.') break;
- else if(c=='E')
- {
- printf("%d",s[1]);
- s[1]=s[len--];
- s_down(1);
- }
- else if(c==' ')
- {
- if(flag==1)
- {
- insert(fh*num);
- num=0;
- flag=0;
- fh=1;
- }
- }
- else
- if(c=='-') fh=-1;
- else{
- flag=1;
- num=num*10+c-'0';
- }
- }
- return 0;
- }
来源: https://www.cnblogs.com/LJA001162/p/12079236.html