题解

思路分析

这是一道 01背包 + 贪心 的组合优化问题。

问题建模

• $n$ 个党派，第 $i$ 个党派有 $a_i$ 个席位
• 联合政府席位数需要 $> \frac{\text{总席位}}{2}$
• 无过剩：移除任何一个党派后，席位数 $\leq \frac{\text{总席位}}{2}$
• 目标：席位数最大的无过剩联合政府

核心思路

1. 无过剩条件

联合政府总席位为 $S$，每个党派席位为 $s_i$，无过剩意味着：

$$S > \frac{\text{total}}{2} \text{ 且 } S - s_i \leq \frac{\text{total}}{2} \quad \forall i $$

变形得：

$$s_i > S - \frac{\text{total}}{2}$$

这意味着每个党派的席位都 必不可少。

2. 贪心策略

要使联合政府席位最大且无过剩，应该：

• 尽量选择席位数相近的党派
• 总席位尽量接近但超过 $\frac{\text{total}}{2}$

3. 01背包求解

按席位数降序排列，使用01背包找到总和最接近但不超过 $\frac{\text{total}}{2}$ 的子集，然后检查是否满足无过剩条件。

状态定义：

• $f[j]$ 表示是否能凑出总和为 $j$ 的席位
• 记录路径以构造方案

4. 方案构造

从背包路径回溯，找到选中的党派。

算法步骤

1. 预处理：

   • 计算总席位 $total$
   • 按席位降序排序

2. 01背包DP：

   • 目标：找到总和最大且 $\leq \frac{total}{2}$ 的子集
   • 记录转移路径

3. 回溯构造方案：

   • 从 $maxn$ 开始回溯
   • 输出选中的党派

复杂度分析

• 时间复杂度：$O(n \cdot \text{total})$
• 空间复杂度：$O(\text{total})$

#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;
}

题解

为保证联合政府中任何一个政党被移出后都无法再保持过半席位，我们只需要找到一个“最小获胜联盟”：总席位数大于全部席位的一半，并且删除任一成员都会回到不超过半数的状态。设总席位数为 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;
}