Codeforcess Goodbye2022 赛后AK 记录

__vector__ · 2022-12-31 12:10:02 · 个人记录

A

显然，每次选择最小的 a_i 进行替换最优。
所以对 a 维护一个小根堆，每次操作取出堆顶，替换掉在扔回堆里就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
const int maxn=105;
int a[maxn],b[maxn];
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        FOR(i,1,n)scanf("%d",&a[i]);
        FOR(i,1,m)scanf("%d",&b[i]);
        sort(a+1,a+n+1);
        priority_queue<int,vector<int>,greater<int> > que;
        FOR(i,1,n)
        {
            que.push(a[i]);
        }
        FOR(i,1,m)
        {
            int u=que.top();
            que.pop();
            u=b[i];
            que.push(u);
        }
        ll ans=0;
        while(!que.empty())
        {
            ans+=que.top();
            que.pop();
        }
        printf("%lld\n",ans);
    }
    return 0;
}

B

思路大概是，可以发现，对于 n \ge 2，代价至少是 n+1。
想想怎样构造才能使 c_i 不超过 n+1。
一个常见的思路是，最大的数配最小的数，次大配次小，\cdots \cdots
也就是 n,1,n-1,2,n-2,3,\cdots\cdots。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
const int maxn=2e5+5;
int t;
int n,k;
int ans[maxn];
bool vis[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        int l=1,r=n;
        while(l<r)
        {
            printf("%d %d ",r,l);
            l++;
            r--;
        }
        if(l==r)
        {
            printf("%d\n",l);
        }
        else printf("\n")
;    }
    return 0;
}

C

待填坑