题目链接:https://ac.nowcoder.com/acm/problem/50940?&headNav=acm
离散化+权值线段树
离散化:排序去重
权值线段树:区间$[l,r]$维护的是有多少个数大于等于$l$且小于等于$r$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e4 + 117;
const int MAXM = 2e5 + 117;
int t;
int id, n, m;
int a[MAXN], b[MAXN], tree[MAXN * 4];
void Hash() {
for(int i = 1; i <= n; i++) b[i] = a[i];
sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - b - 1;
memset(tree, 0, sizeof(tree));
}
int gethash(int x) {
return lower_bound(b + 1, b + 1 + m, x) - b;
}
void update(int i, int l, int r, int x) {
tree[i]++;
if(l == r) return;
int mid = (l + r) / 2;
if(x <= mid) update(i * 2, l, mid, x);
else update(i * 2 + 1, mid + 1, r, x);
}
int query(int i, int l, int r, int k) {
if(l == r) return l;
int mid = (l + r) / 2;
if(k <= tree[i * 2]) return query(i * 2, l, mid, k);
else return query(i * 2 + 1, mid + 1, r, k - tree[i * 2]);
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &id, &n);
printf("%d %d\n", id, n / 2 + 1);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
Hash();
for(int i = 1; i <= n; i++) {
update(1, 1, m, gethash(a[i]));
if(i % 2 != 0)
printf("%d ", b[query(1, 1, m, i / 2 + 1)]);
if(i % 20 == 0) putchar(10);
}
putchar(10);
}
return 0;
}
对顶堆
学习到了新的知识。
- 把序列按值的大小分成两个堆,两个堆的大小相差不超过1。
- 值小的一部分用大顶堆维护,这样堆顶的值是小的一部分中的最大值。
- 值大的一部分用小顶堆维护,这样堆顶的值是大的一部分中的最小值。
- 整个序列的中位数一定是较大的一个堆的堆顶。
记录一个小bug:
vector<int> v;
for(int i=0;i<v.size();i++);
会报warning: comparison between signed and unsigned integer expressions
priority_queue<int> a,b;
if(a.size() - 1 > b.size());
会进行无符号数运算。。。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e4 + 117;
const int MAXM = 2e5 + 117;
int t;
int id, n, x;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &id, &n);
printf("%d %d\n", id, n / 2 + 1);
priority_queue<int> big;//存小的一半
priority_queue<int, vector<int>, greater<int>> small;//存大的一半
for(int i = 1; i <= n; i++) {
scanf("%d", &x);
if(big.empty() || x <= big.top()) big.push(x);
else small.push(x);
if(big.size() > small.size() + 1) {
small.push(big.top());
big.pop();
}
if(small.size() > big.size() + 1) {
big.push(small.top());
small.pop();
}
if(i & 1) printf("%d ", big.size() > small.size() ? big.top() : small.top());
if(i % 20 == 0) putchar(10);
}
putchar(10);
}
return 0;
}
版权属于:小影
本文链接:http://kindkidll.com/index.php/archives/145/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。