最开始的想法是枚举中位数,单调队列计算lower,bigger值
O(n2)时间复杂度,硬着头皮写了出来
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 100005, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int n, m, f;
PII cow[N];
int lower[N], bigger[N];
priority_queue<int> pq;
int main() {
cin >> n >> m >> f;
for (int i = 0; i < m; i++)
cin >> cow[i].first >> cow[i].second;
sort(cow, cow + m);
for (int i = 0; i < m; i++)
{
while (pq.size())pq.pop();
int total = 0;
lower[i] = bigger[i] = INF;
for (int j = 0; j < i; j++)
{
pq.push(cow[j].second);
total += cow[j].second;
if (pq.size() > n / 2) {
total -= pq.top();
pq.pop();
}
lower[i] = (pq.size() == n / 2 ? total : INF);
}
while (pq.size())pq.pop();
total = 0;
for (int j = m - 1; j > i; j--) {
pq.push(cow[j].second);
total += cow[j].second;
if (pq.size() > n / 2) {
total -= pq.top();
pq.pop();
}
bigger[i] = (pq.size() == n / 2 ? total : INF);
}
}
for (int i = m - 1; i >= 0; i--)
if (lower[i] + bigger[i] + cow[i].second <= f) {
cout << cow[i].first << endl;
break;
}
return 0;
}
优化到O(n)
不先枚举中位数,而是预处理lower,bigger数组
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 100005, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int n, m, f;
PII cow[N];
int lower[N], bigger[N];
priority_queue<int> pq;
int main() {
cin >> n >> m >> f;
for (int i = 0; i < m; i++)
scanf("%d%d", &cow[i].first, &cow[i].second);
sort(cow, cow + m);
int total = 0;
for (int i = 0; i < m; i++)
{
lower[i] = (pq.size() == n / 2 ? total : INF);
total += cow[i].second;
pq.push(cow[i].second);
if (pq.size() > n / 2)
{
total -= pq.top();
pq.pop();
}
}
total = 0;
while (pq.size())pq.pop();
for (int i = m - 1; i >= 0; i--)
{
bigger[i] = (pq.size() == n / 2 ? total : INF);
total += cow[i].second;
pq.push(cow[i].second);
if (pq.size() > n / 2)
{
total -= pq.top();
pq.pop();
}
}
bool has_ans = false;
for (int i = m - 1; i >= 0; i--)
if (lower[i] + bigger[i] + cow[i].second <= f) {
cout << cow[i].first << endl;
has_ans = true;
break;
}
if (!has_ans)cout << -1 << endl;
return 0;
}