Hướng dẫn giải của [VTT Q4 Contest 12] Bài 3: Thi đấu cầu lông [BADMINTON]
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
Cần đếm số cặp ~i < j~ thỏa ~a_i + a_j > b_i + b_j~. Đặt ~c_i = a_i - b_i~ thì điều kiện trở thành ~c_i + c_j > 0~, và thứ tự các chỉ số không còn quan trọng.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Duyệt mọi cặp ~i < j~ và kiểm tra ~c_i + c_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)~
Vì chỉ đếm cặp nên sắp xếp ~c~ tăng dần. Đặt con trỏ ~l~ ở đầu, ~r~ ở cuối. Nếu ~c_l + c_r > 0~ thì mọi phần tử từ ~l~ đến ~r-1~ ghép với ~r~ đều thắng, cộng ~r - l~ vào đáp án rồi giảm ~r~; ngược lại tăng ~l~. Đáp án có thể đến khoảng ~2 \times 10^{10}~ nên phải dùng long long. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu, tính ~c~, rồi gọi sub1 khi ~n \le 1000~, ngược lại gọi sub2. 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;
long long a[200005], b[200005], c[200005];
// Sub 1: vét cạn mọi cặp i < j — O(n^2)
void sub1() {
long long cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (c[i] + c[j] > 0) cnt++;
printf("%lld\n", cnt);
}
// Sub 2: đặt c = a - b, điều kiện thành c_i + c_j > 0; sắp xếp rồi hai con trỏ — O(n log n)
void sub2() {
sort(c, c + n);
long long cnt = 0;
int l = 0, r = n - 1;
while (l < r) {
if (c[l] + c[r] > 0) { cnt += r - l; r--; } // mọi l..r-1 ghép với r đều thắng
else l++;
}
printf("%lld\n", cnt);
}
int main() {
freopen("BADMINTON.INP", "r", stdin);
freopen("BADMINTON.OUT", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
for (int i = 0; i < n; i++) scanf("%lld", &b[i]);
for (int i = 0; i < n; i++) c[i] = a[i] - b[i];
if (n <= 1000) sub1();
else sub2();
}
Bình luận