题解 P4394 【[BOI2008]Elect 选举】
ShineEternal
2019-10-03 19:59:31
[这里阅读大概更好](https://blog.csdn.net/kkkksc03/article/details/102013751)
## description：
N个政党要组成一个联合内阁，每个党都有自己的席位数.
现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好.
对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.
## solution：
由于删除任意一个都要保证小于等于一半，所以只要保 证删除最小的那个后小于等于一半即可。
我们可以将所有党按照席位数从大到小排序，之后维护 一个$01$背包。
fj表示通过前i大的党组成席位总数为j的内阁所占的席位
$f_j=max(f_j,(f_j-a_i)+a_i)$
之后枚举满足$f[j]−ai \leq \frac{sum2}{2}$ 并且$f[j] > \frac{sum2}{2}$ 的所有$f[j]$，取最大值
时间复杂度$O(n*∑︀a_i)$，空间复杂度$O(∑︀a_i)$。
## code:
```cpp
#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;
}
```
## description：
N个政党要组成一个联合内阁，每个党都有自己的席位数.
现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好.
对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.
## solution：
由于删除任意一个都要保证小于等于一半，所以只要保 证删除最小的那个后小于等于一半即可。
我们可以将所有党按照席位数从大到小排序，之后维护 一个$01$背包。
fj表示通过前i大的党组成席位总数为j的内阁所占的席位
$f_j=max(f_j , (f_j−a_i)+a_i)$
之后枚举满足$f[j] −ai ≤ \frac{sum2}{2}$ 并且$f[j] > \frac{sum2}{2}$ 的所有$f[j]$，取最大值
时间复杂度$O(n*∑︀a_i)$，空间复杂度$O(∑︀a_i)$。
## code:
```cpp
#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;
}
```