题目分析

先考虑弱化版，记总席位数为 $sum$。不难想到背包 DP，但不过剩的条件难以用背包 DP 处理，即任意党派被移出后，剩余席位数不大于 $\frac{sum}2$。注意到该条件只需考虑移出席位数最小的党派，可以将党派按席位数降序排序，这样席位数最小的党派就是枚举到的最后一个党派，可以用背包 DP 处理。

具体地，设 $f_{i,j}$ 表示是否存在仅由前 $i$ 个党派组成的不过剩的联合政党，满足其席位数之和为 $j$，状态转移方程：

$$\begin{align*}&f_{0,0}=1,\\&f_{i,j}=\begin{cases}f_{i-1,j},&j-a_i>\frac{sum}2\\f_{i-1,j}\vee f_{i-1,j-a_i}.&j-a_i\le\frac{sum}2\end{cases}\end{align*}$$

实现中，通过倒序遍历 $j$，省略数组 $f_{i,j}$ 的一个维度。时间复杂度为 $\mathcal{O}(n\cdot sum)$，空间复杂度为 $\mathcal{O}(sum)$。

本题较弱化版多了输出联合政党的描述的要求，只需额外做下面的事：

1. 排序时，保留索引；
2. 设 $g_{i,j,k}$ 表示 $f_{i,j}=1$ 对应的联合政党是否包含编号为 $k$ 的政党；
3. 背包 DP 时，若 $f_{i,j}\ne f_{i-1,j}$，置 $g_{i,j,k}=g_{i-1,j-a_i,k}\vee[k=i]$；
4. 根据 $g_{i,j,k}$ 进行输出。

实现中，同样省略数组 $g_{i,j,k}$ 的一个维度，还可以将数组 $f_{i,j}$ 和数组 $g_{i,j,k}$ 放在结构体中转移。时间复杂度、空间复杂度均为 $\mathcal{O}(n\cdot sum)$，可以通过本题。

AC 代码

#include<algorithm>
#include<iostream>
using namespace std;
const int N=300+10,M=1e5+10;
int n,sum,ans,cnt;
struct Party{
    int val,index;
    bool operator<(const Party &other)const{
        return val>other.val;
    }
} a[N];
struct State{//结构体方便转移
    char d[N>>3];
    bool get(int index){//index == 0 表示 f_{i,j}，否则表示 g_{i,j,index}
        return d[index>>3]>>(index&7)&1;
    }
    void set(int index){
        d[index>>3]|=1<<(index&7);
    }
} b[M>>1],ans_state;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].val;
        a[i].index=i;
        sum+=a[i].val;
    }
    sort(a+1,a+n+1);
    b[0].set(0);
    for(int i=1;i<=n;i++){
        for(int j=sum>>1;j+a[i].val>sum>>1;j--){//更新 ans 和 ans_state
            if(j+a[i].val<=ans)break;
            if(!b[j].get(0))continue;
            ans=j+a[i].val;
            ans_state=b[j];
            ans_state.set(i);
        }
        for(int j=sum>>1;j>=a[i].val;j--){//DP
            if(b[j].get(0)||!b[j-a[i].val].get(0))continue;
            b[j]=b[j-a[i].val];
            b[j].set(i);
        }
    }
    for(int i=1;i<=n;i++)cnt+=ans_state.get(i);
    cout<<cnt<<'\n';
    for(int i=1;i<=n;i++){
        if(ans_state.get(i))cout<<a[i].index<<' ';
    }
}

#include <bits/stdc++.h>
#define fr first
#define sc second

using namespace std;

const int MAXN = 3e2 + 10;
const int MAXM = 1e5 + 10;
pair<int, int> a[MAXN];
int dp[MAXM];
int n, h, ans;
queue<int> q;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].fr;
        h += a[i].fr;
        a[i].sc = i;
    }
    sort(a + 1, a + 1 + n, greater<pair<int, int>>());
    dp[0] = n + 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = h / 2 + a[i].fr; j >= a[i].fr; j--) {
           if (!dp[j] && dp[j - a[i].fr]) dp[j] = i;
        }
    }
    for (int i = h; i >= 0; i--) {
        if (dp[i]) {
            while(i) {
                q.push(a[dp[i]].sc);
                i -= a[dp[i]].fr;
            }
            break;
        }
    }
    cout << q.size() << endl;
    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    cout << endl;
    return 0;
}