A. Profitable Interest Rate
题意：
Alice有 \(a\) 元钱。
银行有两种业务：
- 业务A:存钱，但是要求最少要存 \(b\) 元
- 业务B:花费x元,使得业务A中的要求 \(b\) 减少 \(2*x\) 元
求Alice最多可以存多少钱
分析
如果Alice要存钱，要使得\((ans=a-x)\)就要大于业务A的要求
\[ \left\{ \begin{matrix} a - x \ge b - 2 x \\ x\ge0 \end{matrix} \right. \Rightarrow x \ge max(b - a,0) \]那么当x取得最小值时，ans最大，即 ans= max(a - max(b - a, 0),0);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
ll a, b;
cin >> a >> b;
cout << max(0ll,a - max(0ll, b - a)) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}
B. Buying Lemonade
题目
有一台柠檬水自动售货机。机器上有 \(n\) 个槽位和 \(n\) 个按钮，每个槽位对应一个按钮，但你并不知道每个按钮对应的是哪个槽位。
当您按下第 \(i\) 个按钮时，有两种可能的事件：
- 若 \(i\) 号槽位有至少一瓶柠檬水，则其中一瓶柠檬水会从这个槽位里掉下来，然后你会把它取走。
- 若 \(i\) 号槽位没有柠檬水，则什么都不会发生。
柠檬水下落速度很快，因此您看不清它从哪个槽位掉出。您只知道每个槽位中瓶装柠檬水的数量 \(a_i (1 \le i \le n)\)。
您需要求出至少收到 \(k\) 瓶柠檬水的最小按按钮次数。
数据保证机器中至少存在 \(k\) 瓶柠檬水。
分析
很简单的一个策略，第一轮按下所有的按钮， 之后每一轮的只按上一轮中，有罐头落下的按钮。这样可以保证在最坏情况下按按钮次数最少。
在这种操作方式下，我们在第 \(i\) 轮会获得饮料的数量\(x\) 即\(a数组中大于等于i的元素个数\)，按按钮的次数会在\(x\)的基础上多出\(y\) ,即\(a数组中等于i-1元素的个数\)，
但是我们并不能一轮一轮模拟，所以我们将\(a\)数组递增排序，相当于是按照按钮被使用完的顺序先后遍历。
统计一下在使用完了第 \(i\) 个按钮后，还需要多少罐头 \(k\)，以及现在按了多少次按钮 \(ans\),
每次计算在 \(i-1\) 按钮使用时，到 \(i\) 个按钮使用完时，可以获得的罐头数量 \(w\) ,即 \((a[i] - a[i - 1])*(n - i + 1)\)，
那么这次操作次数就是在这次获得的具体罐头数加上上一个按钮被最后按下的那一次，当然 \(i=1\) 时没有上一个按钮。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
void solve()
{
int n, k; cin >> n >> k;
vector<ll> a(n + 1, 0);
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(a.begin() + 1, a.end());
ll ans = 0;
for(int i = 1; i <= n; i ++) {
ll w = 1ll * (a[i] - a[i - 1]) * (n - i + 1);
if(k <= w) {
ans += k + (i != 1);
break;
} else {
ans += w + (i != 1);
k -= w;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}