题解 P4664 【[BalticOI 2008]选举 Hard】

· · 题解

提供一个比较不一样的背包解法：（时空都是O(n))

当第i个党派是过剩党派的时候，那么满足不等式：

k - a_i\leq s/2

（其中a_i是党派的人数，s是总人数，k是联合政府人数）

这个是很显然的

对于一个确切的a_i，我们能知道这个a_i，在k等于什么的时候，这个a_i是可以被选进联合政府的（也就是说肯定不会是过剩党派）

其实就是变形一下:

a_i \leq k \leq a_i + s/2

（左边要大于等于a_i是因为既然要选a_i那肯定有a_i个嘛）

考虑暴力，我们只用枚举k，然后先用上述的不等式挑选出合适的党派，然后再跑一个01背包，看看能不能刚好凑到k人。但是这样肯定复杂度不对。

我们突然发现，好像可以不枚举这个k，直接跑01背包，找出最大能到达的背包状态（也就是最大的k）不就可以了吗。其实这中间有后效性问题，我们拿样例举例：

4
1 3 2 4

他们分别对应的最大k值是（其实就是s/2+a_i）：

6 9 7 8

在最后一个4的时候，它可以和3组成7，这是合法的，答案也是这个。

但是按照01背包，他和1、2组成7也是可以的，但是这里的问题是，1的最大k是6，而现在k已经到7了，也就是说其实是非法的。看来如果直接做01背包会有后效性。

现在问题变成了，有一堆物品，有重量，但是某些物品在背包重量大于等于某个值的时候是非法的。要解决这个问题也很简单，因为我们的不等式太简单了。

只要按“对应的最大k值”（其实就是把a_i）从大到小排序，再按顺序做01背包就可以消除后效性了。一个物品在塞入背包的时候，之前的物品的最大k值肯定比它大，所有这个物品可以随意组合在它自己的最大k值内的物品。

最后一个问题就是输出方案的问题：其实我们上面的背包只用记录存不存在就可以了，这个背包是没有类似标准01背包那样还有价钱的。我们只用在背包的权值处记录这个重量其实是加了某个物品a_i以后到达的，那我们每次减去a_i就可以慢慢回溯到背包的0重量状态。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=305,MAXT=1e5+5;
pii a[MAXN];//（结构体都懒得写.jpg）
int bag[MAXT];
int ans[MAXN],tail;
int n,s,mx;

signed main(void)
{
    cin>>n;
    for(int i=1,x;i<=n;i++) scanf("%d",&x),s+=x,a[i]={x,i};
    sort(a+1,a+n+1),bag[0]=n+1;
    for(int i=n;i>=1;i--)
        for(int k=s/2+a[i].first;k>=a[i].first;k--)
            if(bag[k-a[i].first]&&!bag[k]) bag[k]=i;
    for(int i=1e5;i>=0;i--)
        if(bag[i]) {mx=i;break;}
    while(mx) ans[++tail]=a[bag[mx]].second,mx=mx-a[bag[mx]].first;
    printf("%d\n",tail);
    for(int i=1;i<=tail;i++) printf("%d ",ans[i]);
    return 0;
}