/** 题目：D - No Need 链接：http://arc070.contest.atcoder.jp/tasks/arc070_b 题意：给出N个数，从中选出一个子集，若子集和大于等于K，则这是一个Good子集，现在要求这N个数里无用数的个数。 无用数的定义是：在这个数所属的所有Good子集中，如果把这个数删去后原子集仍然是一个Good子集，它就是一个无用数 思路：关键点是存在单调性，如果某个数是必须的，那么比他大的数都是必须的； 证明如下：假设x是必须的，y是比x大的某个数；x是必须的，即x和其他某些数合成的和s加起来为sum>=k，且这个总和sum是满足>=k的情况中最小的和;且s<k; 如果某些数包含了y，那么把y去掉后，肯定是sum-y<k；所以y是必须的。 如果某些数不包含y，那么把x去掉后，再加上y，肯定是>=k的，因为y>=x； 所以存在单调性。 这样就可以二分+bitset优化判断。（bitset用于求组合数的和） */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<bitset> using namespace std; const int maxn = 5005; const int inf = 0x3f3f3f3f; typedef long long ll; int a[maxn]; int n , k; int b[maxn]; bitset<maxn> dp; int judge(int x) { if(a[x]>=k) return 1; ///剔除当前数，剩余的数dp一发；存在性判断. dp.reset(); dp[0] = 1; for(int i = 0; i < n; i++){ if(i==x) continue; dp|=(dp<<a[i]); } for(int i = k-1; i >= k-a[x]; i--){ if(dp[i]){ return 1; } } return 0; } int solve() { sort(a,a+n); /* int lo = -1, hi = n; while(hi-lo>1){ int m = (lo+hi)/2; if(judge(m)) hi = m; else lo = m; } return hi; */ int lo = 0, hi = n-1; int mas = -1;///这里必须-1，因为我后面+1了，如果不这样的话，结果>=1; while(lo<=hi){ int m = (lo+hi)/2; if(judge(m)) hi = m-1; else{ lo = m+1; mas = max(mas,m); } } return mas+1;///下标是mas，所以要再加一； } int main() { while(scanf("%d%d",&n,&k)==2) { for(int i = 0; i < n; i++){ scanf("%d",&a[i]); } printf("%d ",solve()); } return 0; }