题目描述
Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi
然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大
Applese觉得这个题依然太菜，于是他把这个问题丢给了你 当物品数量为偶数时，中位数即中间两个物品的价值的平均值
输入描述:
第一行三个数v, n, m，分别代表背包容量，物品数量以及需要取出的物品数量 接下来n行，每行两个数ai，bi，分别代表物品价值以及大小 n
≤ 1e5, 1 ≤ m ≤ n, ai ≤ 1e9, v ≤ 1e9, bi ≤ v
输出描述:
仅一行，代表最大的中位数
示例1
输入
20 5 3
3 5
5 6
8 7
10 6
15 10
输出
8
题解：
第一反应感觉是二分
m有奇数偶数两种情况
当m是奇数时，左右分别取m/2个，最中间的就是我们要的答案
当m为偶数时，左边取m/2-1个，右边取m/2个，中位数为两个数，就是当前第i个数和右边第一个数（因为我们枚举时只能选定一个，所以就通过选定第i个把第i+1也确定）
接下来详细讲讲过程
x[i]表示物品最小体积的前缀和
y[]表示物品最小体积的后缀和
对于每一个位置，我们枚举左右两边体积最小的m/2个数，（因为左右两边体积越小，给中间留的越多）
我们可以用优先队列，从小到大依次放入，当背包容量不够时，去掉最大值，依次这样操作，留到最后的就是合理值
当求奇数时，枚举每个位置，如果左右两边m/2个和中间的大小符合条件，则说明满足条件。取最大的中间值
当求偶数时，最终答案是两个数的平均值，我们枚举这两个中左边的数，左边取m/2-1个右边取m/2个。我们的序列是经过排序的，右边的第一个数取的越靠右
中位数就越大，但是越靠右他的物品总大小一定不会减少中位数就越大，但是越靠右他的物品总大小一定不会减少
可以发现，右边选取物品的总大小是一个递增的可以发现，右边选取物品的总大小是一个递增的
与此同时，他的价值也是递增的，那么可以发现与此同时，他的价值也是递增的，那么可以发现应该在大小符合的条件下尽量往右选，这就是明显的二分啊应该在大小符合的条件下尽量往右选，这就是明显的二分，直接二分右边第一个的位置找到尽量靠右的合法位置即可
题解借鉴
代码:
代码是有问题的，但是我看了一阵子也没找出来。。。
#include<bits/stdc++.h>
const int maxn= 1e5+2;
typedef long long ll;
using namespace std;
struct node{
ll a,b,id;
}w[maxn];
ll x[maxn],y[maxn];
//x表示前i个数（含第i个）取m/2个物品其大小的和的最小值
//y表示后i个数（含第i个）取m/2个物品其大小的和的最小值
bool cmp1(node a1,node b1)
{
return a1.a<b1.a;//按照 价值排序
}
priority_queue<int>q;
long long int v,n,m;
//v n m
ll solve1(){
ll sum=0;
for(int i=m+1;i<=n-m;i++)
{
if(x[i-1]+y[i+1]+w[i].b<=v)sum=w[i].a;//枚举中间值，再上左右两边，看看有没有超过背包容量
return sum;
}
}
ll solve2(){
ll sum=0;
for(int i=m;i<=n-m;i++){
int l=i+1;
int r=n-m+1;
while(l<=r){
//偶数有两个中位数，先确定一个，然后二分另外一个
int mid=(r+l)>>1;
if(x[i-1]+y[mid]+w[i].b<=v)l=mid+1;//如果没超过背包的体积，说明中间值还可以更大
else r=mid-1;//否则更小
}
if(r>i)sum=max(sum,w[i].a+w[r].a);//中间两个值和的最大值
}
return sum/2;
}
int main()
{
cin>>v>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>w[i].a>>w[i].b;
}
sort(w+1,w+1+n,cmp1);
int z=m&1;
m>>=1;
for(int i=1;i<=n;i++)
{
q.push(w[i].b);
x[i]=x[i-1]+w[i].b;
if(q.size()>m-1+z)
{
x[i]-=q.top();
q.pop();
}
}
while(!q.empty())q.pop();
for(int i=n;i;i--){
q.push(w[i].b);
y[i]=y[i+1]+w[i].b;
if(q.size()>m)
{
y[i]-=q.top();
q.pop();
}
}
if(z)
{
cout<<solve1();
}
else
{
cout<<solve2();
}
return 0;
}
京公网安备 11010502036488号