题解

为保证联合政府中任何一个政党被移出后都无法再保持过半席位，我们只需要找到一个“最小获胜联盟”：总席位数大于全部席位的一半，并且删除任一成员都会回到不超过半数的状态。设总席位数为 num，半数为 hlf = num / 2，把各政党按席位从大到小排序后，用 0/1 背包扩展所有可能的席位和。数组 f[s][0] 记录第一次凑出席位和 $s$ 时最后加入的政党编号，f[s][1] 记录该政党的席位数。遍历每个政党时对 $j$ 从 $\min(hlf, num - seat)$ 递减，如果 $j$ 已可达且 $j + seat$ 还没有被填充，就把新状态写入。因为政党按席位降序枚举，每个席位和只会被第一次到达的方案保留下来，从而保证得到的总席位最大；与此同时一旦移除任何一个政党都会回到某个 $j \le hlf$ 的旧状态，自然不再过半。最终的 $maxn$ 即为满足条件的最大席位和，沿着 $f$ 数组逆向回溯即可输出联盟中所有政党的编号。

#include<bits/stdc++.h>
using namespace std;
const int N=305;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int n,num,f[100005][2],maxn;
vector<int> ans;
struct node
{
    int v,wz;
}a[N];
bool cmp(node ai,node bi){return ai.v>bi.v;}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i].v=read(),num+=a[i].v,a[i].wz=i;
    sort(a+1,a+n+1,cmp);
    int hlf=num/2;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        // cout<<a[i].v<<' '<<a[i].wz<<endl;
        for(int j=min(hlf,num-a[i].v);j>=0;j--)
            if(f[j][0]&&!f[j+a[i].v][0]) f[j+a[i].v][0]=a[i].wz,f[j+a[i].v][1]=a[i].v,maxn=max(maxn,j+a[i].v);//,cout<<j<<' '<<j+a[i].v<<endl;
        // cout<<endl;
    }
    int dq=maxn;
    while(dq)
    {
        // cout<<dq<<endl;
        ans.push_back(f[dq][0]);
        dq-=f[dq][1];
    }
    write(ans.size()),puts("");
    for(int i=0;i<ans.size();i++) write(ans[i]),printf(" ");
    return 0;
}