AT_arc070_b

_Above_the_clouds_ · 2023-05-07 12:04:38 · 个人记录

思路：

这题就是求在某个集合里，去掉 {a_i} 后，如果和还大于等于 k，那么 ans++,最后输出 ans。

那怎么计算出可有可无数呢？为了使可有可无数最多，集合里的所有数的和就要尽可能越大，所以应该从大到小排序，再用 sum 记录每个集合的和，如果 sum 加上 {a_i} 后大于等于k,说明这个集合已经满了，ans 就重新赋值为 0，否则， sum 就加上 {a_i}，可有可无数的数量加一，也就是 ans++。

代码：

#include<bits/stdc++.h>
using namespace std;
const int Max=1e5+5;
int n,k,ans;
long long sum;//计算每个集合的和
int a[Max];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];//输入
    sort(a+1,a+n+1);//排序
    for(int i=n;i;i--)//从大到小计算
        if(sum+a[i]>=k) ans=0;//sum大于等于k,ans就归零
        else{
            sum+=a[i];//和加上a[i]
            ans++;//可有可无数加一
        }
    cout<<ans;//输出  
    return 0;
}