中位数C++题解

T3 中位数

题目描述：
在玩正整数。他手里有一个串，每次会实施三种操作中的一种。

1. 把没有加入的最小的正整数，从左边加入串中。
2. 把没有加入的最小的正整数，从右边加入串中。
3. 询问此时串的最中间的数，也就是假设当前有 个数，输出第
   个数。
   他会进行 次操作，对于每次3操作，输出询问值。
   输入格式
   第一行包含一个整数 。
   之后的 行每行首先包含一个整数 。
   输出格式
   对于每个3操作，输出询问值。
   样例
   样例输入1
   6
   1
   1
   1
   3
   2
   3
   样例输出1
   2
   1
   思路：用一个数组要开到2e6, 因为前后各自1e6，定义两个指针h，t，如果是1，q[–h] = x;如果是2，q[++t] = x;
   如果是3,求ht中间点做为数组下标。
   注意，输入要用scanf，输出用printf，不然会tle的很惨，考试因为没用scanf只得了55pts。
   ac代码如下：

#include 
using namespace std;
int q[2000010];
int n;
int id;
int cnt = 1;
int h, t;
int main() {
	freopen("middle.in", "r", stdin);
	freopen("middle.out", "w",stdout);
	scanf("%d", &n);
	id = 1e6 + 1;
	h = id, t = id + 1;
	for(int i = 1; i <= n; i++) {
		int op;
		scanf("%d", &op);
		if(op == 1) {
			q[h] = cnt;
			h--;
			cnt++;
		}
		if(op == 2) {
			q[t] = cnt;
			t++;
			cnt++;
		}
		if(op == 3) {
			printf("%d\n", q[h + (int)(ceil((double)((t - h) / 2.0)))]);
		}
	}
//	cout << h <<" " <<  t << endl;
//	for(int i = h; i <= t; i++) {
//		cout << q[i] << " ";
//	}
	return 0;
}
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