黑匣子
Description
我们使用黑匣子的一个简单模型. 它能存放一个整数序列和一个特别的变量 i. 在初始时刻, 黑匣子为空且 i 等于 0. 这个黑匣子执行一系列的命令. 有两类命令:
(1)ADD(x): 把元素 x 放入黑匣子;
(2)GET:i 增 1 的同时, 输出黑匣子内所有整数中第 i 小的数.
牢记第 i 小的数是当黑匣子中的元素以非降序排序后位于第 i 位的元素 (输入数据保证每次 GET 命令中第 i 小的数必存在)
Input
输入的第 1 行只有一个整数 n, 表示有 n 条命令. 第 2 行至第 n+1 行, 每行一条命令.
Output
- Sample Input
- 11
- ADD(3)
- GET
- ADD(1)
- GET
- ADD(-4)
- ADD(2)
- ADD(8)
- ADD(-1000)
- GET
- GET
- ADD(2)
- Sample Output
- 3 3 1 2
- HINT
- Source
- #include<bits/stdc++.h>
- using namespace std;
- int s1[500001], s2[500001], len1 = 0,len2 = 0;
- void s1_up(int p)
- {
- while(p>1&&s1[p/2]>s1[p])
- {
- swap(s1[p/2],s1[p]);
- p=p/2;
- }
- return;
- }
- void s1_down(int p)
- {
- int lt;
- while(1)
- {
- if(p*2>len1) return;
- if(p*2==len1) lt=p*2;
- else
- {
- if(s1[p*2]<s1[p*2+1])
- lt=p*2;
- else
- lt=p*2+1;
- }
- if(s1[p]>s1[lt])
- {
- swap(s1[p],s1[lt]);
- p=lt;
- }
- else break;
- }
- return;
- }
- void s1_insert(int key)
- {
- s1[++len1]=key;
- s1_up(len1);
- }
- void s2_up(int p)
- {
- while(p>1&&s2[p/2]<s2[p])
- {
- swap(s2[p/2],s2[p]);
- p=p/2;
- }
- return;
- }
- void s2_down(int p)
- {
- int lt;
- while(1)
- {
- if(p*2>len2) return;
- if(p*2==len2) lt=p*2;
- else
- {
- if(s2[p*2]>s2[p*2+1])
- lt=p*2;
- else
- lt=p*2+1;
- }
- if(s2[p]<s2[lt])
- {
- swap(s2[p],s2[lt]);
- p=lt;
- }
- else break;
- }
- return;
- }
- void s2_insert(int key)
- {
- s2[++len2]=key;
- s2_up(len2);
- }
- int main()
- {
- int n;
- cin>>n;
- char tmp[10];
- gets(tmp);
- int k=1;
- for(int i=1;i<=n;i++)
- {
- char c;
- scanf("%c",&c);
- if(c=='A')
- {
- int x;
- scanf("DD(%d)",&x);
- gets(tmp);
- if(x<s2[1]) s2_insert(x);
- else s1_insert(x);
- }
- else
- {
- gets(tmp);
- while(len2<k)
- {
- int x=s1[1];
- s1[1]=s1[len1--];
- s1_down(1);
- s2_insert(x);
- }
- while(len2>k)
- {
- int x=s2[1];
- s2[1]=s2[len2--];
- s2_down(1);
- s1_insert(x);
- }
- printf("%d\n",s2[1]);
- k++;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3344082.html