우리가 n개의 팀을 가지고 있고 우리가 항상 다소 약한 팀과 플레이하도록 다소 강한 팀을 배치한다고 가정합니다. 예를 들어 순위 1의 팀이 순위 n의 팀과 플레이하게 하는 것과 같이 이 전략은 대회를 더 흥미롭게 만드는 것입니다. 이제 우리는 문자열 형태로 그들의 최종 대회 경기를 찾아야 합니다.
이 팀은 초기 순위를 나타내는 1에서 n까지의 양의 정수 형태로 제공됩니다. 따라서 1순위가 가장 강한 팀이고 n순위가 가장 약한 팀입니다. 괄호와 쉼표를 사용하여 대회 팀 페어링을 나타냅니다. 페어링에는 괄호('(', ')')를, 파티션에는 쉼표(',')를 사용합니다. 각 라운드의 짝짓기 과정에서 우리는 항상 강한 쪽과 약한 쪽을 만드는 전략을 따라야 합니다.
따라서 입력이 4와 같으면 출력은 ((1,4), (2,3))
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
create() 함수를 정의하면 low, high, array v2, array v1,
가 필요합니다. -
낮음>=높음이면 -
-
반환
-
-
v2 끝에 "(" 연결 v1[low] 연결 ", " v1[high] 연결 ") 삽입
-
생성(낮음 + 1, 높음 - 1, v2, v1)
-
주요 방법에서 다음을 수행하십시오 -
-
어레이 v1, v2 정의
-
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
-
삽입 변환 i를 v1의 끝에 문자열로 삽입
-
-
v1> 1의 크기인 동안 −
-
생성(0, v1, v2, v1의 크기)
-
v1 :=v2
-
v2 어레이 지우기
-
-
v1의 마지막 요소를 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void create(int low, int high, vector <string>& v2, vector <string>& v1){
if (low >= high)
return;
v2.push_back("(" + v1[low] + "," + v1[high] + ")");
create(low + 1, high - 1, v2, v1);
}
string findContestMatch(int n) {
vector v1, v2;
for (int i = 1; i <= n; i++) {
v1.push_back(to_string(i));
}
while (v1.size() > 1) {
create(0, v1.size() - 1, v2, v1);
v1 = v2;
v2.clear();
}
return v1.back();
}
};
main(){
Solution ob;
cout << (ob.findContestMatch(4));
} 입력
4
출력
((1,4),(2,3))