自动搬运

查看原文

来自洛谷，原作者为

	PBCWZCC 做你自己

搬运于2025-08-24 21:59:43，当前版本为作者最后更新于2018-07-05 15:51:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

人生第一道深蓝祭

这题是个01背包。

题目说的意思是，联合内阁占有的席位要超过总席位数的一半，但去掉最小的已选入内阁的党，剩下的席位要小于一半。

现将所有的席位数排序，再用背包处理一下，这样在占有席位数恰好超过一半时，最后选入的党席位数最小（这部分详见代码里的注释，本蒟蒻语文太差）。

下面是源代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int p[301];
int mid;
int f[100001];
int maxx;
int summ;
int max_(int a,int b)
{
	return a<b?b:a;
}
int mt[100011];
int main()
{
	scanf("%d",&n);
	for(register int i(1);i<=n;++i)
	{
		scanf("%d",&p[i]);
		summ += p[i];
	}
	mid = summ>>1;
	sort(p+1,p+1+n);//排序，保证最后加进内阁的党的席位数最小
	for(int i(n);i>=1;--i)//先把大的党加进去，越往后越小
	{
		for(int j(summ);j>=0;--j)
		{
			if(j-p[i]>=0)
			{
				f[j] = max_(f[j],f[j-p[i]]+p[i]);
			}
			if(f[j]>mid&&f[j]-p[i]<=mid)//加上较小的党，内阁占有席位恰好超过一半；如果在加上这个党派之前内阁席位小于总数一半，就更新答案
			{
				maxx = max_(maxx,f[j]);//更新答案
			}
		}
	}
	printf("%d",maxx);
	return 0;
}

话说这题是怎么深蓝的