题解 AT2346【[ARC070B] No Need】

zhaoyp · 2022-10-03 08:28:43 · 题解

Description

给定一个大小为 n 的正整数集合，一个元素和不小于 k 的非空子集被称为优秀的，问有多少个元素满足把它改成 0 而不会影响优秀子集的个数。

Solution

有一个重要的性质：若 x 是必须的，则比 x 大的所有数都是必须的。

设最小的一个必须的数为 x。

考虑一个含有 x 的优秀的集合且其他元素的和小于 k，由于 x 是必须的，所以这样的集合一定存在。集合里的元素都是必须的，那么 x 是集合里最小的数。

把 x 替换成其它任意比 x 大的数，显然新集合也是不可删数的优秀的集合，可知替换上的元素也是必须的。

于是我们只要将 a 降序排序之后找最后一个必须的数 x 的位置。

考虑它的一个必要条件：

比 x 大的数可以组成一个和小于 k 大于等于 k - x 的集合（含空集）。

然后一边扫一边做背包就行了，时间复杂度 O(nk)。

可以用bitset优化到 O(n \log n)。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
int f[maxn],n,k,a[maxn],cnt; 
bool cmp(int a,int b){return a > b;}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    sort(a + 1,a + 1 + n,cmp);
    f[0] = 1;
    for(int i = 1;i <= n;i++)
    {
        if(a[i] >= k)
            cnt = i;
        else 
            for(int j = k - 1;j >= k - a[i];j--)
                if(f[j])
                    {cnt = i;break;}
        for(int j = k;j >= a[i];j--)
            f[j] |= f[j - a[i]];
    }
    cout << n - cnt;
    return 0 ;
}