Giả sử chúng ta có n đội và chúng ta luôn sắp xếp đội khá mạnh đấu với đội khá yếu, giống như để đội hạng 1 đấu với đội hạng n, chiến lược này là làm cho cuộc thi trở nên thú vị hơn. Bây giờ chúng ta phải tìm các trận đấu cuối cùng trong cuộc thi của họ dưới dạng một chuỗi.
Các đội này được đưa ra dưới dạng các số nguyên dương từ 1 đến n, đại diện cho thứ hạng ban đầu của họ. Vì vậy, hạng 1 là đội mạnh nhất, và hạng n là đội yếu nhất. Chúng tôi sẽ sử dụng dấu ngoặc đơn và dấu phẩy để đại diện cho việc ghép nối đội dự thi - dấu ngoặc đơn ('(‘,') ') để ghép nối và dấu phẩy (', ') để phân vùng. Trong quá trình bắt cặp ở mỗi vòng, chúng tôi luôn phải tuân theo chiến lược chọn cặp đôi khá mạnh với cặp đôi khá yếu.
Vì vậy, nếu đầu vào là 4, thì đầu ra sẽ là ((1,4), (2,3))
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm create (), điều này sẽ lấy thấp, cao, mảng v2, mảng v1,
-
nếu thấp> =cao, thì -
-
trở lại
-
-
insert "(" concatenate v1 [low] concatenate "," concatenate v1 [high] concatenate ") vào cuối v2
-
tạo (thấp + 1, cao - 1, v2, v1)
-
Từ phương thức chính, thực hiện như sau -
-
Xác định mảng v1, v2
-
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
-
chèn chuyển đổi i thành chuỗi ở cuối v1
-
-
trong khi kích thước v1> 1, do -
-
tạo (0, kích thước của v1, v2, v1)
-
v1:=v2
-
xóa mảng v2
-
-
trả về phần tử cuối cùng của v1
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
4
Đầu ra
((1,4),(2,3))