[ 백준 28449 ] 누가 이길까 (c/c++)

https://www.acmicpc.net/problem/28449

 

 

[ 문제 요약 ]

HI팀과 ARC팀의 인원 수와 각각의 실력이 주어질 때 다른 팀의 모든 사람들과 한번씩 대결을 한다. 첫째 줄에 HI팀 참가자의 승리 횟수, ARC팀 참가자의 승리 횟수, 무승부 횟수를 공백으로 구분하여 출력한다.

 

 

[ 문제 풀이 ]

1. 두 개의 팀원의 실력을 입력받아 정렬을 한 뒤 하나의 팀을 기준으로 잡는다.

2. 한 명에 대해서 이분 탐색을 하여서 그 사람이 질 때마다 그 위치를 기록한다.

3. 반대로 동일 인물에 대해서 이분 탐색을 하여서 그 사람이 이길 때마다 그 위치를 기록한다.

4. 질 때마다 기록한 위치는 그 사람이 속한 팀이 이긴 횟수이고 M - 이길 때마다 기록한 위치는 상대팀이 이긴 횟수이다.

5. 이길 때마다 기록한 위치 - 질 때마다 기록한 위치 + 1은 비긴 횟수이다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M;
long long Hwin = 0, Awin = 0, draw = 0;
int HI[101010], ARC[101010];

int main() {
	cin >> N >> M;

    for (int i=0; i<N; i++) cin >> HI[i];
    for (int i=0; i<M; i++) cin >> ARC[i];
    sort(HI, HI+N);
    sort(ARC, ARC+M);

    for (int i=0; i<N; i++){
        int low = 0, high = M - 1;
        int left = M;
        
        while (low <= high){
            int mid = (low + high) / 2;
            if (ARC[mid] >= HI[i]) {
                left = mid;
                high = mid - 1;
            }
            else low = mid + 1;
        }

        low = 0; high = M - 1;
        int right = -1;
        
        while (low <= high){
            int mid = (low + high) / 2;
            if (ARC[mid] <= HI[i]) {
                right = mid;
                low = mid + 1;
            }
            else high = mid - 1;
        }
        Hwin += left;
        draw += (right - left + 1);
        Awin += (M - right - 1);
    }
    cout << Hwin << " " << Awin << " " << draw;
    
	return 0;
}

 

 

[ 주의할 점 ]

이분 탐색과 누적합을 같이 써야 한다. 또한 누적합이기 때문에 범위는 long long으로 해야 한다.