CF2024A#

题意简述#

Alice有 $a$ 枚硬币，她想要将硬币存入银行，但是开立存款的最低金额为 $b$ ，如果金额不足，可以花费 $x$ 个硬币使得存款的最低金额减少 $2x$ 。求存入银行的最大硬币数量。

题意分析#

显然，当 $b\le a$ 时，可以直接将 $a$ 枚硬币全部存入，所以直接输出 $a$ 即可。

反之，当 $b>a$ 时，我们需要花费硬币降低最低金额。不难发现，题目要求最大值，且同时符合单调性，可以使用二分答案来直接计算。答案区间表示存入银行的硬币数量 $ans$ ，通过check判断 $ans$ 与 $b-(a-ans)\times 2$ 的大小关系，如果 $ans\ge b-(a-ans)\times 2$ ，check判断为true，将左边界更新即可。

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
bool check(int x)
15
{
16
    if(x>=M-(N-x)*2){
17
        return 1;
18
    }
19
    return 0;
20
}
21
inline void Solve()
22
{
23
  cin>>N>>M;
24
    if(N>=M){
25
        cout<<N<<endl;
26
    }
27
    else{
28
        int l=0,r=N;
29
        while(l<r){
30
            int mid=(l+r+1)>>1;
31
            if(check(mid)){
32
                l=mid;
33
            }
34
            else{
35
                r=mid-1;
36
            }
37
        }
38
        cout<<l<<endl;
39
    }
40
}
41
signed main()
42
{
43
#ifndef ONLINE_JUDGE
44
    freopen(".in", "r", stdin);
45
    freopen(".out", "w", stdout);
46
#endif
47
    ios::sync_with_stdio(0);
48
    cin.tie(0),cout.tie(0);
49

50
#ifdef MULTI_CASES
51
    cin >> T;
52
    while (T--)
53
#endif
54
       Solve();
55
    //fclose(stdin);
56
    //fclose(stdout);
57
    return 0;
58
}