[codeforce] D.Devu and his Brother

문제링크

풀이

에딧을 보고 푼 문제. 삼분탐색을 잘 몰랐는데 좋은 걸 배웠다.

다음에 한번 다시 풀기 위해 기록.

주어진 함수가 convex임을 확인한 다음, 3분탐색을 통해 구현.

Proof.

It is fairly easy to prove. See the derivative of f.

 = — (# of elements of b > k) + (# of elements of a < k)

The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases.

So, 

소스코드

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int N=(int)1e5+10;
ll a[N];
ll b[N];
int n,m;
 
ll func(ll k)
{
    ll ans=0;
    for(int i=0;i<n;i++){
        if(a[i]<k)
            ans+=k-a[i];
    }
    for(int i=0;i<m;i++){
        if(b[i]>k)
            ans+=b[i]-k;
    }
    return ans;
 
}
 
 
 
 
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int j=0;j<m;j++)
        cin>>b[j];
    ll ans=1e18;
    ll lo=1;
    ll hi=1e9;
    for(int i=0;i<100;i++){
        ll mid1=lo+(hi-lo)/3;
        ll mid2=hi-(hi-lo)/3;
        if(func(mid1)<ans)
            ans=func(mid1);
        if(func(mid2)<ans)
            ans=func(mid2);
        if(func(mid1)>=func(mid2))
            lo=mid1;
        else
            hi=mid2;
    }
    cout<<ans;
}