AT2346 No Need

atcoder上的题目

链接

一道思维题目

可以发现如果X是可有可无的，那么所有小于X的数也一定是可有可无的，

所有我们只要找出最大的那个可有可无的数字就好了

进一步分析，发现

若A1, A2, . . . , Ai 的和为 S，当且紧当 Ai+1, Ai+2, . . . , AN 凑不出任何个 K − S 到 K − 1 之间的数字， A1, A2, . . . , Ai 都是可有可无的。

我们来不太严谨的证明一下

若A1, A2, . . . , Ai 的和为 S，如果 Ai+1, Ai+2, . . . , AN 凑不出任何个 K − S 到 K − 1 之间的数字，那么 A1, A2, . . . , Ai 都是可有可无的。

这显然是成立的

当sum=Ai+1, Ai+2, . . . , AN 凑出任何个 K − S 到 K − 1 之间的数字时，我们一定有sum+s>=K

我们从小到大将sum+s减去Ai，一定会有一个j使得sum+s<k那么Aj就一定不是可有可无的

我们将A从小到大排序

01背包就好了

一个小技巧，0一定是可有可无的，所以循环到0是一定会输出，可以适当代码更加优美

# include<iostream>

# include<cstdio>

# include<cmath>

# include<algorithm>

# include<cstring>

using namespace std;

const int mn = ;

int a[mn];

bool vis[mn];

int n,k,s;

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++)

    {

      scanf("%d",&a[i]);

      a[i]=min(a[i],k);

      s+=a[i];

    }

    sort(a+,a++n);

    vis[]=;

    for(int i=n;i>=;i--)

    {

        bool flag=false;

        for(int j=k-;j>=k-s && j>=;j--)

           if(vis[j]) {

           flag=true;

           break;

           }

        if(!flag)

        {

            printf("%d",i);

            return ;

        }

        for(int j=k;j>=a[i];j--)

           vis[j]=(vis[j] | vis[j-a[i]]);

        s-=a[i];

    }

    return ;

}

巴特西

AT2346 No Need

最新文章

热门文章