Nối Điểm Đen Trắng (VOI 2011)
Đề bài
Trên trục số thực cho $n$ điểm đen và $n$ điểm trắng hoàn toàn phân biệt. Các điểm đen có toạ độ nguyên $a_1, a_2, \ldots, a_n$ còn các điểm trắng có toạ độ nguyên $b_1, b_2, \ldots, b_n$. Người ta muốn chọn ra $k$ điểm đen và $k$ điểm trắng để nối mỗi một điểm đen với một điểm trắng sao cho $k$ đoạn thẳng tạo được đôi một không có điểm chung.
Kết quả: ghi ra một số nguyên duy nhất là số $k$ lớn nhất tìm được.
Input
- Dòng thứ nhất chứa số nguyên dương $n$ $(n \le 10^5)$.
- Dòng thứ hai chứa các số $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9, i = 1, 2, \ldots, n)$.
- Dòng thứ ba chứa các số $b_1, b_2, \ldots, b_n$ $(|b_i| \le 10^9, i = 1, 2, \ldots, n)$.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Output: cho toạ độ của $n$ điểm đen $a_1, a_2, \ldots, a_n$ và toạ độ của $n$ điểm trắng $b_1, b_2, \ldots, b_n$, hãy tìm giá trị $k$ lớn nhất thoả mãn yêu cầu trên.
Giới hạn: 50% số test ứng với 50% số điểm của bài có $1 \le n \le 100$.
3
0 3 1
-3 5 -12Note: hình minh hoạ cho ví dụ (chấm đen là điểm đen, chấm rỗng là điểm trắng):
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm toàn bộ phần hướng dẫn để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 🥰. Chúc các bạn học tốt và gặt hái nhiều thành công.
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên VNOJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngTham lam: nối điểm ngoài lề với điểm khác màu gần nhất
Với bài này tư tưởng của nó là THAM LAM và có dùng đến kỹ thuật sắp xếp trong quá trình triển khai. Mấu chốt là tấm hình minh hoạ ví dụ ở cuối đề em thấy không? Em nhìn vào ví dụ sẽ thấy quy luật của nó.
Nếu sắp toạ độ các điểm trên trục số theo thứ tự tăng dần từ trái qua phải như trong hình, thì khi em gặp điểm trắng đầu tiên, hợp lý nhất là nối nó với điểm đen đầu tiên đúng không? Tức là sắp xếp các điểm tăng dần, sau đó đi từ điểm ở ngoài lề: nếu đó là điểm trắng thì nối nó với điểm đen gần nhất tính từ nó.
- Ngoài lề là $-3$ đang là điểm trắng, đi lên gặp điểm đen đầu tiên là $0$, nối tụi nó với nhau.
- Nối xong thì xét điểm kế tiếp điểm 0 là điểm 1, đang là điểm đen, cần tìm điểm trắng gần nhất, đi lên gặp điểm 5.
- Tổng cộng có 2 đoạn nối được tạo ra và tụi nó không bị cắt nhau.
Minh hoạChạy tay thuật toán từng bước
Em nhập toạ độ các điểm đen và điểm trắng (mỗi loại tối đa 10 điểm, các điểm khác nhau) rồi bấm Tiếp để xem thuật toán quét từ trái sang phải:
CodeCài đặt
Ý tưởng là vậy, anh đã code xong và nộp test thử AC. Em có thể tự code trước, không ra có thể tham khảo code của anh, không hiểu chỗ nào thì em có thể hỏi anh sẽ giải đáp cho em nha:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 5;
pair<int, bool> a[MAX];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int sz = 2 * n;
for(int i = 0; i < n; ++i){
cin >> a[i].first;
a[i].second = true;
}
for(int i = n; i < sz; ++i){
cin >> a[i].first;
a[i].second = false;
}
sort(a, a + sz);
int res = 0;
bool flag = a[0].second;
for(int i = 1; i < sz; ++i){
if(a[i].second == !flag){
res++;
if(i + 1 < sz){
flag = a[i + 1].second;
}
}
}
cout << res;
return 0;
}import sys
input = sys.stdin.read
data = list(map(int, input().split()))
n = data[0]
x = data[1:1 + n]
y = data[1 + n:1 + 2 * n]
combined = [(val, 1) for val in x] + [(val, 0) for val in y]
combined.sort(key=lambda pair: pair[0])
res = 0
flag = combined[0][1]
i = 1
while i < 2 * n:
if combined[i][1] != flag:
res += 1
i += 1
if i < 2 * n:
flag = combined[i][1]
i += 1
print(res)Có thể hiểu true là điểm đen, false là điểm trắng. a[i] có kiểu pair (kiểu cấu trúc có 2 thành phần là first và second): first anh để lưu toạ độ điểm, còn second anh đánh dấu để biết nó là điểm đen hay trắng. Cứ nhét hết toàn bộ tụi nó vào mảng, khi gọi sort thì mặc định nó sẽ sort theo thành phần first tức là toạ độ. Sau khi sort xong thì các a[i].first tăng dần, lúc này chỉ cần xét a[i].second là biết đó là điểm đen hay trắng.
Xét danh sách các vị trí từ nhỏ đến lớn, đầu tiên là a[0], giả sử a[0].second đang là true, thì anh tiếp tục xét lên a[1], a[2]… cho đến khi gặp thằng a[i] nào mà second của nó là false (ngược với a[0].second) thì xem như tụi nó nối với nhau. Chọn xong thì gán lại cờ hiệu flag lưu màu của thằng a[i+1] tiếp theo, lại tiếp tục tìm từ i+2 trở lên thằng đầu tiên có màu ngược với flag thì lại nối được với nhau, và cứ thế… Sau cùng sẽ biết có bao nhiêu cặp điểm thoả mãn.
Độ phức tạpCó kịp 1 giây không?
- Bước đọc dữ liệu: $O(2N)$.
- Bước sort: $O(2N \log(2N))$.
- Bước duyệt tìm đáp án: $O(2N)$.
Tổng quát ta lấy theo cái lớn nhất là $O(2N \log 2N)$. Với $N$ tối đa $10^5$ thì $2N \log 2N \approx 34 \cdot 10^5$, tức khoảng 3 triệu rưỡi phép tính, trong khi giới hạn 1 giây được tối đa khoảng 100 triệu, nên yên tâm không bị TLE.
Mình đã kiểm tra cả 2 bản code với 500 bộ test ngẫu nhiên so với cách quy hoạch động vét cạn mọi cách nối, đều cho cùng kết quả; với $n = 10^5$, bản C++ chạy khoảng 0.03 giây, bản Python khoảng 0.2 giây.