สมมุติว่าเรามี n ทีมและเรามักจะจัดทีมที่ค่อนข้างแข็งแกร่งให้เล่นกับทีมที่ค่อนข้างอ่อนแอ เช่น ให้ทีมอันดับ 1 เล่นกับทีมที่มีอันดับ n กลยุทธ์นี้จะทำให้การแข่งขันน่าสนใจยิ่งขึ้น ตอนนี้เราต้องหาแมตช์สุดท้ายของการแข่งขันในรูปแบบของสตริง
ทีมเหล่านี้จะได้รับในรูปแบบของจำนวนเต็มบวกตั้งแต่ 1 ถึง n ซึ่งแสดงถึงอันดับเริ่มต้น ดังนั้น อันดับ 1 คือทีมที่แข็งแกร่งที่สุด และอันดับ n คือทีมที่อ่อนแอที่สุด เราจะใช้วงเล็บและลูกน้ำเพื่อแสดงการจับคู่ทีมแข่งขัน - วงเล็บ ('(', ')') สำหรับการจับคู่ และเครื่องหมายจุลภาค (',') สำหรับการแบ่งพาร์ติชัน ในระหว่างกระบวนการจับคู่ในแต่ละรอบ เรามักจะต้องปฏิบัติตามกลยุทธ์ในการสร้างคู่ที่แข็งแกร่งกับคู่ที่อ่อนแอ
ดังนั้น หากอินพุตเท่ากับ 4 เอาต์พุตจะเป็น ((1,4), (2,3))
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน create() ซึ่งจะใช้เวลาต่ำ สูง อาร์เรย์ v2 อาร์เรย์ v1
-
ถ้าต่ำ>=สูง แล้ว −
-
กลับ
-
-
แทรก "(" concatenate v1[low] concatenate "," concatenate v1[high] concatenate ") ที่ส่วนท้ายของ v2
-
สร้าง(ต่ำ + 1, สูง - 1, v2, v1)
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
กำหนดอาร์เรย์ v1, v2
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=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))
