P5941

_Violet_Evergarden · 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;
}