AT2346 [ARC070B] No Need

Tx_Lcy · 2022-07-14 08:17:29 · 个人记录

独一无二的贪心做法。

思路

不难想象，假如包含 a_i 的所有集合内去掉 a_i，这个集合的总和依然大于等于 k，a_i 就是可有可无的。所以，我们先把它排个序，对于每一个 i\ \ (1 \le i \le n)，我们从后往前计算除它以外的数之和，若和大于等于了 k，我们选择最小的，即排完序后最靠前的那个数删掉。

因为以我们贪心的思路，我们想要凑出一个值尽可能接近于 k，但又略小于 k，以便于此时 a_i 与此值的和有最大的概率大于 k。

若此时的和加上 a_i 就大于等于了 k，那么 a_i 一定不是可有可无的。

排序复杂度 O(n \log n)，判断复杂度 O(n^2)，总复杂度 O(n^2)，可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rint register int
int const N=5e3+10;
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;cin>>n>>k;
    for (rint i=1;i<=n;++i) cin>>a[i];
    sort(a+1,a+n+1);
    if (n==1){
        if (a[1]>=k) cout<<0<<'\n';
        else cout<<1<<'\n';
        return 0;
    }//特判，不然会 WA 四个点
    int ans=0;
    for (rint i=1;i<=n;++i){
        int sum=0,tag=1;
        for (rint j=n;j>=1;--j){
            if (j==i) continue;
            sum+=a[j];
            if (sum>=k) sum-=a[j];
            if (sum+a[i]>=k){
                tag=0;
                break;
            }
        }
        ans+=tag;
    }
    cout<<ans<<'\n';
    return 0;
}