洛谷P4394 [BOI2008]Elect 选举 题解

description：

N个政党要组成一个联合内阁，每个党都有自己的席位数.

现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好.

对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.

solution：

由于删除任意一个都要保证小于等于一半，所以只要保 证删除最小的那个后小于等于一半即可。

我们可以将所有党按照席位数从大到小排序，之后维护 一个 $01$01背包。

fj表示通过前i大的党组成席位总数为j的内阁所占的席位

$f_j=max(f_j,(f_j-a_i)+a_i)$fj​=max(fj​,(fj​−ai​)+ai​)

之后枚举满足 $f\left[j\right]-ai\le \frac{sum2}{2}$f[j]−ai≤2sum2​ 并且 $f\left[j\right]>\frac{sum2}{2}$f[j]>2sum2​ 的所有 $f\left[j\right]$f[j]，取最大值

时间复杂度 $O(n\ast \sum ︀a_i)$O(n∗∑︀ai​)，空间复杂度 $O(\sum ︀a_i)$O(∑︀ai​)。

code:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[305];
int f[100005];
int main()
{
	int n,sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		//f[a[i]]=1;
		sum+=a[i];
	}
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=n;i>=1;i--)
	{
		for(int j=sum;j>=a[i];j--)
		{
			f[j]=max(f[j],f[j-a[i]]+a[i]);
			if(j-a[i]<=sum/2&&f[j]>sum/2)
			{
				ans=max(ans,f[j]);
			}
		} 
	} 
	printf("%d\n",ans);
	return 0;
}