利用两个优先队列，可以求出数组中第k小的数字
解题思路
利用两个优先队列当大根堆和小根堆，将前k个数字放入大根堆中，再将剩下的数字放入小根堆中，大根堆的堆顶就是所求。
题意：有n个数字（n为奇数）组成的数组，当遍历到奇数索引时，中位数是多少。
思路：用一个大根堆维护较小部分数字，小根堆维护较大部分的数字。插入时根据插入的元素与两个优先队列堆顶元素的大小关系插入指定序列。插入之后维护两个堆，使大根堆的大小为小根堆+1.
注意：STL的优先队列的greater模式，堆顶是最小值；less模式，堆顶是最大值。不要用反！！
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
using namespace std;
const int N = 1000000;
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--)solve();
cout.flush();
return 0;
}
int num[N];
void solve()
{
int testcase,n;
cin>>testcase>>n;
veci ans;
priority_queue<int,veci, less<int> > big;
priority_queue<int,veci, greater<int> > small;
int x;
cin>>x;
big.push(x);
for(int i=1;i<n;i++)
{
if(i&1)
{
while(big.size()>small.size()+1)
{
small.push(big.top());
big.pop();
}
while(small.size()+1>big.size())
{
big.push(small.top());
small.pop();
}
ans.push_back(big.top());
}
cin>>x;
if(x>big.top())small.push(x);
else big.push(x);
}
while(big.size()>small.size()+1)
{
small.push(big.top());
big.pop();
}
while(small.size()+1>big.size())
{
big.push(small.top());
small.pop();
}
ans.push_back(big.top());
cout<<testcase<<' '<<ans.size();
for(int i=0;i<ans.size();i++)
{
if(i%10==0)cout<<endl;
cout<<ans[i]<<' ';
}
cout<<endl;
}
|
【POJ1442】Black Box
题意：一个数组，m次询问。对于第i次询问，输出当插入到第i个数字的时候，数组第i小的数字是多少。
思路：跟中位数一样，用两个优先队列维护数组。但是这题可以先全部插入到一个堆中，然后再维护两个堆，使其中一个堆存放前i小的数字，其堆顶就是所求。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #ifdef VLSMB_VS
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1000000;
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
while(t--)solve();
cout.flush();
return 0;
}
int num[N];
void solve()
{
int m,n;
cin>>m>>n;
veci a(m),u(n);
for(int i=0;i<m;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>u[i];
priqgi big;
priqli small;
int cur=0;
for(int i=0;i<n;i++)
{
while(cur<u[i])
{
if(small.empty()||a[cur]>=small.top())big.push(a[cur]);
else small.push(a[cur]);
cur++;
}
while(small.size()<i+1)
{
small.push(big.top());
big.pop();
}
while(small.size()>i+1)
{
big.push(small.top());
small.pop();
}
cout<<small.top()<<endl;
}
}
|
