自动搬运

查看原文

来自洛谷，原作者为

	CodyTheWolf ACM在役的小动物！qwq

搬运于2025-08-24 22:02:25，当前版本为作者最后更新于2021-01-06 09:05:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一个比较不一样的背包解法：（时空都是$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;
}