백준 28449 누가 이길까 C++

간단한 해설

 

 

HI팀이 이기는 경우랑 무승부만 세면 자연스럽게 ARC팀이 이기는 경우의 수가 나온다.(전체 경우의 수인 N*M에서 빼면 된다.)

 

이 때, 전체 경우의 수는 100,000*100,000 이므로 int 자료형의 범위를 넘어가니 long long 형으로 해야한다.

 

HI팀이 이기는 경우의 수는 누적합을 써도 좋지만 나는 간단하게 이분탐색으로 찾았다.

 

upper_bound의 결과값 - lower_bound의 결과값을 하면 간단하게 무승부인 경우의 수를 셀 수 있고,

lower_bound의 결과값이 이기는 경우의 수이다.

 

lower_bound는 같거나 큰 값만을 탐색하므로 결과값에서 -1을 해야 하는게 맞지만 Index를 반환하기 때문에(Index가 0부터 시작해서) 따로 처리를 안해주고 결과값 그 자체가 이기는 걍우의 수이다.

 답

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll n,m;
    cin>>n>>m;
    vector<int> a(n);
    vector<int> b(m);
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    for(int i=0;i<m;++i){
        cin>>b[i];
    }
    sort(b.begin(),b.end());
    ll aWin=0,bWin=0,mu=0;
    for(int i=0;i<n;++i){
        auto lo=lower_bound(b.begin(),b.end(),a[i])-b.begin();
        auto hi=upper_bound(b.begin(),b.end(),a[i])-b.begin();
        ll gae=hi-lo;
        mu+=gae;
        if(lo>0){
            aWin+=lo;
        }
    }
    bWin=m*n-aWin-mu;
    cout<<aWin<<" "<<bWin<<" "<<mu;
}