POJ 2010 优先队列

题目链接:http://poj.org/problem?id=2010

有 $C$ 个物品,每个物品有价值和价格两个属性。从中选出 $n$($n$ 为奇数)个物品,使得这 $n$ 个物品的价值中位数尽量高,且总价格不超过 $f$。

思路

由于 $n$ 是奇数,我们可以枚举中位数。中位数之前必有 $\lfloor\frac{n}{2}\rfloor$ 个数,中位数之后必有 $\lfloor\frac{n}{2}\rfloor$ 个数。

首先将整个序列按照价值排序,选定某个中位数,接下来就是要从这个中位数之前选出 $\lfloor\frac{n}{2}\rfloor$ 个价格之和最小的数,从这个中位数之后选出 $\lfloor\frac{n}{2}\rfloor$ 个价格之和最小的数。如果前后数,带上本身的价格总和满足题意,那就可以记录答案。

到这一步就有了两种解法。

优先队列

用一个优先队列维护前 $\lfloor\frac{n}{2}\rfloor$ 个数的价格最小值。随着中位数的右移来更新这个优先队列。对于之后的 $\lfloor\frac{n}{2}\rfloor$ 也是如此。

数组 $l[i]$ 表示从前 $i$ 个物品中选出 $\lfloor\frac{n}{2}\rfloor$ 个物品的价格之和的最小值;数组 $r[i]$ 表示从后 $i$ 个物品中选出 $\lfloor\frac{n}{2}\rfloor$ 个物品的价格之和最小值。

priority-queue.cppview raw
#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
#define maxc 100005
#define maxn 20005
#define ll long long
using namespace std;

pair<int, int> stu[maxc];
int n, c, f;
ll l[maxc], r[maxc];

void work_l() {
ll fsum = 0;
priority_queue<int, vector<int> > q;
for (int i = 0; i < n / 2; i++) {
q.push(stu[i].second);
fsum += stu[i].second;
}
l[n / 2] = fsum;
for (int i = n / 2; i < c - 1; i++) {
if (q.top() > stu[i].second) {
fsum -= q.top();
q.pop();
fsum += stu[i].second;
q.push(stu[i].second);
}
l[i + 1] = fsum;
}
}

void work_r() {
ll fsum = 0;
priority_queue<int, vector<int> > q;
for (int i = c - 1; i >= c - n / 2; i--) {
q.push(stu[i].second);
fsum += stu[i].second;
}
r[c - n / 2 - 1] = fsum;
for (int i = c - n / 2 - 1; i > 0; i--) {
if (q.top() > stu[i].second) {
fsum -= q.top();
q.pop();
fsum += stu[i].second;
q.push(stu[i].second);
}
r[i - 1] = fsum;
}
}

int main() {
scanf("%d %d %d", &n, &c, &f);
for (int i = 0; i < c; i++)
scanf("%d %d", &stu[i].first, &stu[i].second);
sort(stu, stu + c);
work_l();
work_r();
int ans = -1;
for (int i = n / 2; i < c - n / 2; i++)
if (l[i] + r[i] + stu[i].second <= (ll) f)
ans = stu[i].first;
printf("%d\n", ans);
return 0;
}

二分搜索

二分中位数。检查如果以这个数为中位数,能否找到满足题意的序列。

为了方便,再将整个序列按照价格从小到大排序。从中依次选出物品,如果该物品在原序列(按照价值排序的序列)中在中位数之前,则 lnum++,否则 rnum++。最后根据 lnumrnum 判断合法性。

binary-search.cppview raw
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define maxc 100005
#define maxn 20005
#define ll long long
using namespace std;

struct student {
int score, finan, id;
}stu_s[maxc], stu_f[maxc];
int n, c, f;

bool cmp_s(const student& a, const student& b) {
return a.score < b.score;
}

bool cmp_f(const student& a, const student& b) {
return a.finan < b.finan;
}

int main() {
scanf("%d %d %d", &n, &c, &f);
for (int i = 0; i < c; i++)
scanf("%d %d", &stu_s[i].score, &stu_s[i].finan);
sort(stu_s, stu_s + c, cmp_s);
for (int i = 0; i < c; i++) {
stu_s[i].id = i;
stu_f[i] = stu_s[i];
}
sort(stu_f, stu_f + c, cmp_f);
int l = 0, r = c - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
int lnum = 0, rnum = 0, totf = stu_s[mid].finan;
for (int i = 0; i < c; i++) {
if (stu_f[i].id < mid && stu_f[i].finan + totf <= f && lnum < n / 2) {
lnum++;
totf += stu_f[i].finan;
}
if (stu_f[i].id > mid && stu_f[i].finan + totf <= f && rnum < n / 2) {
rnum++;
totf += stu_f[i].finan;
}
}
if (lnum < n / 2 && rnum < n / 2) {
break;
} else if (rnum < n / 2) {
r = mid - 1;
} else if (lnum < n / 2) {
l = mid + 1;
} else {
ans = max(ans, stu_s[mid].score);
l = mid + 1;
}
}
printf("%d\n", ans);
return 0;
}