刷题记录:牛客NC17315背包

传送门:牛客

题目描述:

Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi
然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要
使得求出来的物品价值的中位数最大
Applese觉得这个题依然太菜，于是他把这个问题丢给了你
当物品数量为偶数时，中位数即中间两个物品的价值的平均值
输入:
20 5 3
3 5
5 6
8 7
10 6
15 10
输出:
8

感觉这道题还是挺难的,思路不好想到.

主要思路:

1. 首先根据我们要求中位数我们显然会想到排序吗,所以我们可以先将物品根据价值进行排序.
2. 假设我们在n个物品中取一个作为我们的中位数(对于这道题,我们奇偶数需要分类,此处是奇数的情况),那么对于这个中位数是否能够成为我们的合法中位数的话,看的是这个中位数前面的数字能否取出m/2个数字满足其的总大小小于我们的V,并且该位置后面也能否取出m/2个数字满足总大小小于我们的V,如果不满足的话,我们往右不断移动即可
3. 下面就是如何计算我们最小质量的总和了,此时我们可以使用单调队列来存储,我们使用一个单调队列从前往后跑,每次都值存储m/2个数字,在每一个位置记录队列中的数字的总和即可(此时存储的从前往后的数字的总和),再从后往前跑,存储方式和之前相同,我们就记录了从后往前的数字的总和,到目前为止我们就解决可奇数的情况了
4. 偶数的情况将要比奇数的情况更加麻烦一点,大部分我们的储存的前后数字的总和的方式是相同的,但是因为偶数情况下我们是有两个中位数的,我们此时肯定是不能直接枚举两个中位数的位置的,因为这样的话我们的最坏复杂度将会被卡成N^2,此时我们选择控制一个中位数(位置在前的那一个),然后去用二分来枚举后面的那一个中位数,此处解释一下二分的正确性:首先我们是将数字按照从小到大来排序的,显然我们的指针越往右那么此时我们的中位数平均值将会越大,并且我们发现右边的数字越多显然越容易满足有m/2个数字满足要求,这就构成了一个单调性,所以我们可以二分,至此我们也解决了偶数的情况,这道题我们就可以快乐的AC了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int v,n,m;
struct Thing{
	int a,b;
}thing[maxn];
bool cmp(Thing x,Thing y) {
	return x.a<y.a;
}
int sum1[maxn],sum2[maxn];
int main() {
	v=read();n=read();m=read();
	for(int i=1;i<=n;i++) {
		thing[i].a=read();thing[i].b=read();
	}
	sort(thing+1,thing+n+1,cmp);
	if(m&1) {
		int ans=-inf;
		priority_queue<int>q;
		for(int i=1;i<=n;i++) {
			sum1[i]=sum1[i-1]+thing[i].b;
			q.push(thing[i].b);
			if(q.size()>m/2) {
				sum1[i]-=q.top();
				q.pop();
			}
		}
		while(q.size()) q.pop();
		for(int i=n;i>=1;i--) {
			sum2[i]=thing[i].b+sum2[i+1];
			q.push(thing[i].b);
			if(q.size()>m/2) {
				sum2[i]-=q.top();
				q.pop();
			}
		}
		for(int i=m/2+1;i<=n-(m/2);i++) {
			if(sum1[i-1]+sum2[i+1]+thing[i].b<=v) {
				ans=max(ans,thing[i].a);
			}
		}
		cout<<ans<<endl;
	}else {
		int ans=-inf;
		priority_queue<int>q;
		for(int i=1;i<=n;i++) {
			sum1[i]=sum1[i-1]+thing[i].b;
			q.push(thing[i].b);
			if(q.size()>m/2-1) {
				sum1[i]-=q.top();
				q.pop();
			}
		}
		while(q.size()) q.pop();
		for(int i=n;i>=1;i--) {
			sum2[i]=thing[i].b+sum2[i+1];
			q.push(thing[i].b);
			if(q.size()>m/2) {
				sum2[i]-=q.top();
				q.pop();
			}
		}
		for(int i=m/2;i<=n-(m/2);i++) {
			int l=i+1,r=n-(m/2)+1;
			while(l<=r) {
				int mid=(l+r)>>1;
				if(sum2[mid]+sum1[i-1]+thing[i].b<=v) {
					ans=max(ans,(thing[mid].a+thing[i].a)/2);
					l=mid+1;
				}else {
					r=mid-1;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0; 
}