题解 | #背包#
背包
https://ac.nowcoder.com/acm/problem/17315
做这道题的时候一开始想到了对顶堆但发现如果根据输入逐步使用对顶堆的话，不好实现最优的选择。
看了题解才知道这不是一道对顶堆的题目，可以使用对物品的价值进行排序，然后某个物品能否作为中位数可以通过向左取(m-1)/2个物品，向右取(m-1)/2个物品。取左右物品的最小重量总和然后加上中位数可以判断这个物品能不能作为中位数。如果可以那么取可以作为中位数中的最大值。
当然如果是偶数的话，我们还需要进行一些处理。因为偶数是两个数的平均数作为中位数，所以我们需要去左右两个数。直接暴力寻找会超时的，所以我们选择遍历一个数，二分去寻找另一个数。然后取他们和的最小值。
如何快速验证某个数能不能作为中位数：可以建立两个前缀和，一个从前向后的(m-1)/2个物品的最小重量总和，一个从后向前的(m-1)/2个物品的最小重量总和。在中间如果超过了(m-1)/2个物品需要取出的话肯定去除最大的那一个，所以可以使用一个优先队列来维护。
//按价值排序，向左边找(m-1)/2个最小重量的物品，向右边找(m-1)/2个最小重量的物品。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
struct Node{
int a, b;
};
const int maxn = 1e5+10;
int v, n, m;
Node a[maxn];
ll sum1[maxn];
ll sum2[maxn];
priority_queue<int> pq;
bool comp(Node x, Node y) {
return x.a<y.a;
}
signed main() {
cin>>v>>n>>m;
for (int i=1;i<=n;i++) {
cin>>a[i].a>>a[i].b;
}
//根据价值排序
sort(a+1, a+n+1, comp);
//用优先队列来计算(m-1)/2个物品的重量和
for (int i=1;i<=n;i++) {
pq.push(a[i].b);
sum1[i] = sum1[i-1]+a[i].b;
if (pq.size()>(m-1)/2) sum1[i] -= pq.top(),pq.pop();
}
//将队列里面的东西全部删除
while (pq.size()) pq.pop();
//从新从后向前计算前缀和
for (int i=n;i>0;i--) {
pq.push(a[i].b);
sum2[i] = sum2[i+1]+a[i].b;
if (pq.size()>(m-1)/2) sum2[i] -= pq.top(),pq.pop();
}
ll ans = 0;
//如果是奇数直接从后向前的找第一个符合条件的就行。
if (m%2) {
for (int i=n-((m-1)/2);i>1+((m-1)/2);i--) {
if (sum1[i-1]+sum2[i+1]+a[i].b<=v) {
ans = a[i].a;
break;
}
}
cout<<ans<<endl;
} else {
//定一个点，然后去二分另一个点
for (int i=1+((m-1)/2);i<n-((m-1)/2);i++) {
int l = i+1, r = n-((m-1)/2);
while (l<r) {
int mid = (l+r+1)/2;
if (sum1[i-1]+sum2[mid+1]+a[i].b+a[mid].b<=v) {
l = mid;
} else {
r = mid-1;
}
}
if (sum1[i-1]+sum2[l+1]+a[i].b+a[l].b<=v) {
//用的到的两点计算总和，力求总和最大
ans = max(ans, ll(a[l].a+a[i].a));
}
}
cout<<ans/2;
}
return 0;
}
投递阿里巴巴控股集团等公司7个岗位 >
滴滴二面48人在聊