题解 P4394 【[BOI2008]Elect 选举】

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

话说这题是怎么深蓝的