题解归档 - cf2229B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2229B
• 本地来源：problems/cf2229B/idea.md
• 题目链接：https://codeforces.com/contest/2229/problem/B
• 原始标题：cf2229B

思路

cf2229B

pattern: pairwise orientation upper bound.

claim: The maximum equals sum(max(a_i,b_i)) + max(min(a_i,b_i)).

necessary: In any final arrangement, suppose max(a) is at pair k. Then max(a)+b_k is at most a_k+b_k, the sum of the two original numbers in pair k. Every other b_i is at most max(a_i,b_i). Therefore the whole value is at most sum(max pair) + min pair at k, and this is at most sum(max pair)+max(min pair).

sufficient: Put the larger number of every pair into b and the smaller into a. Then sum(b)=sum(max pair) and max(a)=max(min pair), attaining the upper bound.

brute/check: For small n enumerate all 2^n swap masks and compare with the formula.

edge: n=1 is covered by x+y.

代码

来源：problems/cf2229B/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
ll a[maxn+5],b[maxn+5];
int main(){
    ll t,n,i,ans,cur;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++) scanf("%lld",&a[i]);
        ans=0;
        cur=0;
        for(i=1;i<=n;i++) scanf("%lld",&b[i]);
        for(i=1;i<=n;i++){
            ans+=max(a[i],b[i]);
            cur=max(cur,min(a[i],b[i]));
        }
        printf("%lld\n",ans+cur);
    }
    return 0;
}