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

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

문제

---

HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다. HI팀엔 N명 ARC팀엔 M명이 속해있다. 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 N×M개의 대결로 이루어진다. 모든 참가자는 코딩실력을 가지고 있다. 대결을 하면 더 높은 코딩실력을 가진 참가자가 승리하고, 두 참가자의 코딩실력이 같다면 무승부가 된다.

하얔이는 이 대회의 결과를 빨리 알고싶어졌다. 하얔이를 위해 대회의 결과를 예측해보자!

 

입력

---

첫째 줄에 HI팀의 인원 수 N, ARC팀의 인원 수 M이 공백으로 구분되어 정수로 주어진다. (1 ≤ N,M ≤ 100000)

둘째 줄에 HI팀의 참가자의 코딩실력을 나타내는 길이 N 수열 a가 공백으로 구분되어 정수로 주어진다. (1 ≤ ai ≤ 100000)

셋째 줄에 ARC팀의 참가자의 코딩실력을 나타내는 길이 M 수열 b가 공백으로 구분되어 정수로 주어진다. (1≤bi≤100000)

 

출력

---

첫째 줄에 HI팀 참가자의 승리 횟수, ARC팀 참가자의 승리 횟수, 무승부 횟수를 공백으로 구분하여 출력한다.

 

문제 풀이

---

이분 탐색 문제.

 

한 사람당 다른 팀 참가자와 모두 한번씩 대결하므로, 한 사람이 이긴 횟수와 무승부 횟수를 구하면 자동적으로 상대팀의 이긴 횟수를 구할 수 있다. lower_bound()와 upper_bound()를 이용하면 같은 숫자의 개수(=무승부 횟수), 이긴 횟수를 구할 수 있으므로 정렬 후 해당 함수를 사용하면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	int* HI = new int[N];
	int* ARC = new int[M];
	long long HIWin = 0;
	long long ARCWin = 0;
	long long draw = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> HI[i];
	}
	sort(HI, HI + N);
	for (int j = 0; j < M; j++)
	{
		cin >> ARC[j];
	}
	sort(ARC, ARC + M);
	for (int i = 0; i < N; i++)
	{
		int upper = upper_bound(ARC, ARC + M, HI[i]) - ARC;
		int lower = lower_bound(ARC, ARC + M, HI[i]) - ARC;
		HIWin += lower;
		draw += upper - lower;
		ARCWin += M - upper;
	}
	cout << HIWin << " " << ARCWin << " " << draw << "\n";
	return 0;
}