CF2024B#

题意简述#

给定 $n$ 个按钮，每个按钮对应 $a_i$ 瓶柠檬水，你不清楚哪个按钮对应哪个 $a_i$ ，按下按钮后，如果有柠檬水就会掉落一瓶，反之则没有任何东西。求至少按多少次按钮可以保证至少收到 $k$ 瓶柠檬水。

题意分析#

首先题目要求保证至少收到 $k$ 瓶，那么我们可以考虑最坏的情况：每次选择一个按钮时都会选择到容量最少的那个。

在这种情况下，我们不可避免的每个按钮多按一次。所以我们可以考虑贪心。首先可以将 $a_i$ 排序，然后从小到大依次更新获取到的柠檬水数量，同时每次将操作次数多加 $1$ 。显然这样不是最优，所以在更新过程中考虑，由于每次读取的都比之后的小，所以如果当前的值乘上剩余的按钮数量再加上已经获得的柠檬水数量之和大于等于 $k$ ，就直接加上 $k$ ，减去已获得的柠檬水数量就是答案。

形式化的说，设操作次数为 $cnt$ ，答案为 $ans$ ，

则对于 $1\le i\le n$ ，若 $ans+(n-i+1)\times a_i<k,ans=ans+a_i,cnt=cnt+a_i+1$ 。

若 $ans+(n-i+1)\times a_i\ge k, cnt=cnt+k-ans$ 此时的 $cnt$ 就是答案。

Code#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
  cin>>N>>M;
17
    for(int i=1;i<=N;i++){
18
        cin>>a[i];
19
    }
20
    sort(a+1,a+N+1);
21
    if(M<=N){
22
        cout<<M<<endl;
23
        return;
24
    }
25
    int ans=0,cnt=0;
26
    for(int i=1;i<=N;i++){
27
        if(cnt+(N-i+1)*a[i]>=M){
28
            ans+=M-cnt;
29
            cout<<ans<<endl;return;
30
        }
31
        cnt+=a[i];
32
        ans+=a[i]+1;
33
    }
34
    cout<<ans<<endl;
35
}
36
signed main()
37
{
38
#ifndef ONLINE_JUDGE
39
    freopen(".in", "r", stdin);
40
    freopen(".out", "w", stdout);
41
#endif
42
    ios::sync_with_stdio(0);
43
    cin.tie(0),cout.tie(0);
44

45
#ifdef MULTI_CASES
46
    cin >> T;
47
    while (T--)
48
#endif
49
       Solve();
50
    //fclose(stdin);
51
    //fclose(stdout);
52
    return 0;
53
}