Hướng dẫn giải của Thi đấu cầu lông (KS THCS 05)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đặt ~d_i = a_i - b_i~. Cặp vận động viên ~(i, j)~ thắng khi ~a_i + a_j > b_i + b_j~, tức ~d_i + d_j > 0~. Cần đếm các cặp không kể thứ tự.
Sub 1: Thử mọi cặp — ~O(n^2)~, dùng khi ~n \le 1000~
Duyệt mọi cặp ~(i, j)~ với ~i < j~ và kiểm tra ~d_i + d_j > 0~. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Sắp xếp và hai con trỏ — ~O(n \log n)~
Sắp xếp ~d~ tăng dần. Nếu ~s_i + s_j > 0~ thì mọi ~s_k~ với ~i \le k < j~ cũng ghép được với ~s_j~, nên cộng ~j - i~ rồi giảm ~j~; ngược lại tăng ~i~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> d; // d[i] = a[i] - b[i]; cap (i, j) thang khi d[i] + d[j] > 0
// Sub 1: thu tat ca cap (i, j), O(n^2) — dung khi n <= 1000
void sub1() {
long long ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (d[i] + d[j] > 0) ans++;
cout << ans << "\n";
}
// Sub 2: sap xep roi dung hai con tro, O(n log n)
void sub2() {
vector<long long> s = d;
sort(s.begin(), s.end());
long long ans = 0;
int i = 0, j = n - 1;
while (i < j) {
if (s[i] + s[j] > 0) { ans += j - i; j--; } // s[i..j-1] cung ghep duoc voi s[j]
else i++;
}
cout << ans << "\n";
}
int main() {
freopen("BADMINTON.INP", "r", stdin);
freopen("BADMINTON.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<long long> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
d.assign(n, 0);
for (int i = 0; i < n; i++) d[i] = a[i] - b[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận