链接:

题目描述

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;
}