Codeforces Round 980 (Div. 2)

糖丸了，什么沟史比赛

A.Profitable Interest Rate

初始有 \(a\) 个硬币，可以花费硬币开通盈利账户与非盈利账户

• 开通盈利账户需要至少花费 \(b\) 个金币
• 开通非盈利账户没有限制
• 每在非盈利账户花费 \(x\) 元，盈利账户的限制 \(b\) 就减少 \(2x\) 元

求最大的在盈利账户上的花费

设盈利花费 \(x\) 元

• \(x\ge b-2(a-x)\)，即 \(x\le 2a-b\)
• \(0\le x\le 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