糖丸了，什么沟史比赛
A.Profitable Interest Rate
初始有 \(a\) 个硬币，可以花费硬币开通盈利账户与非盈利账户
- 开通盈利账户需要至少花费 \(b\) 个金币
- 开通非盈利账户没有限制
- 每在非盈利账户花费 \(x\) 元，盈利账户的限制 \(b\) 就减少 \(2x\) 元
求最大的在盈利账户上的花费
设非盈利花费 \(x\) 元
- \(a-x\ge b-2x\)，即 \(x\ge b-a\)
- \(0\le x\le a\)
根据这两个条件选择最大的 \(a-x\) 值即可
#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);int t;cin>>t;while(t--){int a,b;cin>>a>>b;int tmp=2*a-b;tmp=max(0,tmp);tmp=min(a,tmp);cout<<tmp<<'\n';}
}
B.Buying Lemonade
有一些按钮和一些售货机，你知道每个售货机装的柠檬汁数量，但是你不知道哪个按钮对应哪个售货机
你可以进行如下操作
- 选一个按钮按下去，如果这个按钮对应的售货机里还有柠檬汁，你就会得到一瓶，否则你什么都不会得到
求出买 \(k\) 瓶柠檬汁所需的最小按按钮次数
注意你可以根据售货机的情况调整结果，比如如果你按一个按钮没有得到柠檬汁，那么你就不会再按这个按钮了
\(N\le 2\times 10^5\)
模一组数据，比如 1 1 5 3 3，首先你知道所有的售货机里的柠檬汁都不少于一个，因此你应该先把每个按钮都按一次，然后你会去尝试哪个是空的，假如你足够倒霉，两个 1 都试出来了，那么你就可以确定剩下的售货机里的剩余柠檬汁都不少于 \(2\) 个，所以把每个非空的按钮按两遍，以此类推
模拟这个过程即可，排序后开桶存储
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200001];
struct node{int cnt,val;
};
vector<node>v;
signed main(){ios::sync_with_stdio(false);int t;cin>>t;while(t--){int n,k;cin>>n>>k;for(int i=1;i<=n;++i){cin>>a[i];}sort(a+1,a+n+1);v.clear();for(int i=1;i<=n;++i){if(v.empty()) v.push_back({1,a[i]});else if(v.back().val==a[i]) v.back().cnt++;else v.push_back({1,a[i]});}int tot=0,cost=0,lst=0,rem=n;for(node i:v){int tmp=(i.val-lst)*rem;if(tot+tmp>=k){cost+=k-tot;break;}tot+=tmp;lst=i.val;cost+=tmp+i.cnt;rem-=i.cnt;}cout<<cost<<'\n';}
}
C.Concatenation of Arrays
给你 \(N\) 个数对，你需要把数对首位拼接起来，最小化逆序对个数
\(N\le 10^5\)
看上去很对的假了的做法：
注意到两个数对交换对全局没有影响，因此写一个 cmp 比较两个数对拼接后的最优拼法，直接排序后输出
看上去很假的对了的做法：
将数对按最大值排序，相等则按最小值排序
不知道为啥这个对了，看上去确实是比较对，等题解出了补一下证明
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
pair<int,int> a[100001];
int c[5];
bool cmp(pair<int,int>a,pair<int,int>b){if(max(a.first,a.second)==max(b.first,b.second))return min(a.first,a.second)<min(b.first,b.second);return max(a.first,a.second)<max(b.first,b.second);
}
signed main(){ios::sync_with_stdio(false);int t;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;++i){cin>>a[i].first>>a[i].second;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;++i){cout<<a[i].first<<' '<<a[i].second<<' ';}cout<<'\n';}
}
D.Skipping
P10381
