自动搬运

查看原文

来自洛谷，原作者为

	_Violet_Evergarden 花无凋零之日,意无传递之时,爱情亘古不变,紫罗兰永世长存

搬运于2025-08-24 22:15:49，当前版本为作者最后更新于2023-08-22 15:31:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

闲来无事写一发题解

简要题意

这道题就是说我们要找到一个序列中最大的数，然后使序列中小于这个数的数相加都凑不出小于这个数且不在这个序列中的数的数，而且序列中的数可以相互表示。然后我们要找到在最大数的前提下取最少的数量的数。

思路

当我们看到序列中不会有大于 $10^4$ 的数时，便很容易可以想到把所有前面选的数能表示的数全部打上标记，在遍历的时候如果在这个数前面有打上标记的数且该数并未出现在序列中就说明现在的数就是最大值，否则判断这个数是否打上标记，如果打上了那就不将它放到答案序列中。因为如果他能被前面的数表示，那么它与前面的数相加能表示的数必然已被打上标记。然后这道题就解决了。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000001];
int b[1000001];
int c[1000001];
int d[1000001];
int e[1000001];
int cnt;
int flag;
int xia;
int x;
int p;
int o=100000001;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>d[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=d[i-1];j<d[i];j++){
			if(b[j]){
//				cout<<j<<"!"<<endl; 
				o=i-1;
				flag=1;
			}
		}
		if(flag){
			break;
		}
		if(b[d[i]]){
			b[d[i]]=0;
			continue;
		}
		e[++cnt]=d[i];
		for(int j=1;j<i;j++){
			b[d[i]+d[j]]=1;
		}
		for(int j=1;j<=10000;j++){
			if(!b[j]&&(j%d[i])==0){
				b[j]=1;
			}
			if(b[j]==1){
//				cout<<j<<endl;
				b[d[i]+j]=1;
			}
		}
		
		b[d[i]]=0;
	}
	cout<<d[min(o,n)]<<endl;
	for(int i=1;i<=cnt;i++){
		cout<<e[i]<<endl;
	}
	return 0;
}