Codeforces Round 980 (Div. 2) A-C 题解

Rating 已经掉了 $100$ 多了，没回升过（悲）

A. Profitable Interest Rate

题意

Alice 有 $a$ 个硬币。她可以开设一个名为“盈利”的银行存款，但开设该存款所需的最低金额为 $b$ 个硬币。

还有一个名为“无利”的存款，可以用 任何 数量的硬币开设。Alice 注意到，如果她用 $x$ 个硬币开设“无利”存款，那么开设“盈利”存款所需的最低金额将减少 $2x$ 个硬币。

换而言之，当 $a<b$ 时，可以选择一个正整数 $x$，使得 $a-x\ge b-2x$

求出她可以存入“盈利”存款 ($b-2x$) 的最大硬币数

思路

分类讨论，当 $a\le b$ 时，答案为 $a$

否则，答案为 $\max (a-(b-a),0)$

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
	int a,b;
	cin>>a>>b;
	if(a>=b){
		cout<<a<<endl;
		return;
	}
	if(a-(b-a)<=0){
		cout<<0<<endl;
	}else{
		cout<<a-(b-a)<<endl;
	}
}
signed main(){
    int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

B. Buying Lemonade

题意

有一个自动售货机出售柠檬水。该机器总共有 $n$ 个槽位。你知道最初第 $i$ 个槽位中有 $a_i$ 罐柠檬水。机器上还有 $n$ 个按钮，每个按钮对应一个槽位，但是你 不知道 哪个按钮对应哪个槽位。

当你按下对应于第 $i$ 个槽位的按钮时，会发生以下两种事件之一：

• 如果第 $i$ 个槽位中有一罐柠檬水，它将掉出来，你可以拿到它。此时，第 $i$ 个槽位中的罐数将减少 $1$。
• 如果第 $i$ 个槽位中没有剩余的柠檬水，则什么也不会掉出来。

按下按钮后，你也无法它是从哪个槽位掉下来的。槽位中的内容对你是隐藏的，因此你无法看到每个槽位中剩余多少罐。你唯一知道的是槽位中的初始罐数：$a_1,a_2,\dots ,a_n$

确定你需要按下的最少按钮次数，以确保你至少能获得 $k$ 罐柠檬水，保证机器中至少有 $k$ 罐柠檬水

图解（意思差不多，槽位实在画不出来 QwQ）：

思路

由于我们无法知道哪个对应哪个，所以就一排全按，看哪个不出水了以后就不按了

注意，不能按最优情况，也就是不能说碰运气碰到最好情况，它问的是最优策略

C++ 代码

代码中 $botnum$ 表示 the number of bottle ，当前已经得到的柠檬水瓶数

$prsnum$ 表示你已经按了按钮多少次，其实就是最终答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
	int n,k;
	map<int,int> num;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		int ai;
		cin>>ai;
		num[ai]++;
	}
	int cnt=n;
	int prv=0;
	vector<pair<int,int> > v;
	for(pair<int,int> x:num){
		v.push_back(make_pair(cnt,x.first-prv));
		prv=x.first;
		cnt-=x.second;
	}
	int botnum=0,prsnum=0;
	for(int i=0;i<v.size();i++){
		if(i==0){
			if(botnum+v[i].second*v[i].first>=k){
				prsnum+=(k-botnum);
				break;
			}else{
				prsnum+=v[i].second*v[i].first;
				botnum+=v[i].second*v[i].first;
			}
		}else{
			prsnum+=v[i-1].first-v[i].first;
			if(botnum+v[i].second*v[i].first>=k){
				prsnum+=(k-botnum);
				break;
			}else{
				prsnum+=v[i].second*v[i].first;
				botnum+=v[i].second*v[i].first;
			}
		}
	}
	cout<<prsnum<<endl;
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

C. Concatenation of Arrays

题意

$n$ 个整数对，你需要将它们排序（设排完序的数组为 $a$ ），使得 符合 以下条件的 $(i,j)$ 最少：

• $i<j$ 且 $a_i>a_j$

思路

蒙了一个，还真对了：按照每一对里最小的元素排序

大概证明思路如下：

设两个数对中的四个数分别为 $a,b,c,d(a\le b\le c\le d)$，然后枚举分别为哪两个数，如 $(a,c)(b,d)$，$(d,a)(b,c)$ 等等

枚举完共 $12$ 种情况后会发现，有 $a$ 的那一对永远排在前面

所以 按照每一对里最小的元素排序 即可

C++ 代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b){
	int p=min(a.x,a.y);
	int q=min(b.x,b.y);
	if(p!=q) return p<q;
    p=max(a.x,a.y);
    q=max(b.x,b.y);
	return p<q;
}
void solve(){
	int n;
	cin>>n;
	vector<pair<int,int> > v;
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		v.push_back(make_pair(a,b));
	}
	sort(v.begin(),v.end(),cmp);
	for(pair<int,int> a:v){
		cout<<a.x<<" "<<a.y<<" ";
	}
	cout<<endl;
}
int main(){
    int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}