题解归档 - cf2229D

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

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

思路

cf2229D

pattern: threshold + local majority reduction.

claim: Fix a value x. A column is + if both numbers are at least x, - if both are less than x, and 0 otherwise. The median merge on threshold states is sign(u+v), with 0 acting as an identity, so mixed columns can be deleted.

necessary: After deleting 0, the operation is equivalent to repeatedly replacing equal adjacent signs by one copy and opposite adjacent signs by the empty string. If the - runs are kept at length at least one, every + symbol contributes one possible positive unit, so a final + needs more + symbols than - runs.

sufficient: Compress each - run to one -, keep all + symbols, then the signed sum is #plus - #minus_runs. If it is positive, cancel/merge adjacent signs to leave one +.

brute/check: The brute enumerates all interval merge results for n<=8; stress compares answers for random arrays.

edge: n=1 is covered because one mixed column has no +, while one all-good column has one + and zero bad runs.

代码

来源：problems/cf2229D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll a[maxn+5],b[maxn+5],n;
ll check(ll x){
    ll i,cnt=0,dq=0,last=0;
    for(i=1;i<=n;i++){
        if(a[i]>=x and b[i]>=x){
            cnt++;
            last=1;
        }
        else if(a[i]<x and b[i]<x){
            if(last!=-1) dq++;
            last=-1;
        }
    }
    return cnt>dq;
}
int main(){
    ll t,i,l,r,mid,ans;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(i=1;i<=n;i++) scanf("%lld",&b[i]);
        l=1;
        r=2*n;
        ans=1;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}