cf980
## A. Profitable Interest Rate（贪心）
题意：给定a和b，a-x=b-2x，a>=b输出a,否则输出a+x
代码：
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;cin >> t;
while (t--){
ll a, b;
cin >> a >> b;
if (a >= b){//a
cout << a << "\n";
}
else{
if (2 * a <= b){
cout << "0\n";
}
else{
ll x = b - a;
cout << a - x << "\n";
}
}
}
return 0;
}
```
## B. Buying Lemonade（二分）
题意：每次按一下会发生以下两种情况之一：
如果第 i个槽位中有一罐柠檬水，它会掉出来，你会拿走它。此时，第
个槽位中的罐子数量减少了 1
如果第 i个槽位中没有剩余的柠檬水罐，则不会掉出任何东西。
按下按钮后，罐子会快速掉出，因此无法追踪它从哪个槽位掉落。槽位的内容隐藏在您的视野之外，因此您无法看到每个槽位中剩余的罐子数量。您唯一知道的是槽位中的初始罐子数量ai，求最少按钮次数
分析：用二分寻找最小操作次数
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N],sum=0;
ll n,k;
ll f(ll x){
sum=0;ll cnt=0;
for(int i=1;i<=n;i++){
if(a[i]<x){
sum+=a[i];cnt++;
if(sum>=k){
return sum;
}
}
else break;
}
sum+=(n-cnt)*(x-1);
if(sum>=k){
return sum;
}
for(int i=cnt+1;i<=n;i++){
sum++;
if(sum>=k){
sum+=cnt;
return sum;
}
}
return 0;
}
void sol(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
ll l=0,r=0x3f3f3f3f;
ll ans=0x3f3f3f3f;
if(k<=n*a[1]){
cout<<k<<endl;
return;
}
while(l<r){
ll mid=(l+r)/2;
if(f(mid)>0)r=mid,ans=min(ans,sum);
else l=mid+1;
}
cout<<f(l)<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--)sol();
return 0;
}
```
## C. Concatenation of Arrays（贪心）
题意：有n个数组，每个数组长度为2，将这些数组连成一个长度为2×n的数组，使得数组中的反转数最小，输出解决方案。
分析：为了让反转数尽量小，让小的数尽量往前放，比较两个数组的最小值，将小的排前面，如果相同就比较另外一个数
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct A{
ll x,y;
}a[N];
bool cmp(A xx,A yy){
if(min(xx.x,xx.y)!=min(yy.x,yy.y)){
return min(xx.x,xx.y)<min(yy.x,yy.y);
}
return max(xx.x,xx.y)<max(yy.x,yy.y);
}
//2 3 4 1 5 10 8 7 9 6
void sol(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
cout<<a[i].x<<" "<<a[i].y<<" ";
}
cout<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--)sol();
return 0;
}
```
## D. Skipping（最短路）
题意：有n个问题，第i个问题的分数为ai，参数为bi，每次可以选择提交问题并获得ai分，或者跳过此题以后也无法交此题，
如果提交第i个问题，系统会查看j<i的问题否则查看j<=bi的问题，计算最高分数
分析：用最短路计算到i点的最少消耗值，即可计算到i点的最高分数
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
void sol(){
int n;cin>>n;
vector<ll>a(n+1),b(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
vector<vector<pair<ll,ll>>>edg(n+1);
for(int i=1;i<=n;i++){//存边
edg[i].push_back({b[i],a[i]});//如果要跳的话就消耗ai
if(i!=1)edg[i].push_back({i-1,0});
}
vector<ll> dp(n + 1, 1e18);
vector<ll> vis(n + 1, 0);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;//存储消耗值与当前结点
dp[1]=0;
q.push({0,1});
while(!q.empty()){
auto [juli,idx]=q.top();
q.pop();
if(vis[idx]==1)continue;//走过了
vis[idx]=1;
for(auto [v,w]:edg[idx]){
if(dp[v]>juli+w){//更新到当前位置的最小消耗值
dp[v]=juli+w;
q.push({juli+w,v});
}
}
}
ll sum=0,ans=0;
for(int i=1;i<=n;i++){
sum+=a[i];
ans=max(ans,sum-dp[i]);
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--)sol();
return 0;
}
```