Trạm phát sóng (Đề tự luyện HSG Tin 12 – Bài 2) – Chặt nhị phân đáp án và tham lam "cột xa nhất"

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 2 (đề tự soạn) Độ khó: Khá Chặt nhị phân đáp án Tham lam Sắp xếp

Đề bài

Trạm phát sóng

Trên trục số có $N$ ngôi nhà ở tọa độ $x_i$ và $M$ cột điện ở tọa độ $p_j$. Thầy Sơn được nhà mạng nhờ lắp trạm phát sóng lên tối đa $K$ cột (mỗi cột tối đa một trạm). Mọi trạm có cùng bán kính nguyên $R \ge 0$; trạm ở cột $p$ phủ nhà $x$ khi $|x - p| \le R$. Tìm $R$ nhỏ nhất để mọi nhà đều có sóng.

Dữ liệu vào: dòng đầu $N, M, K$ $(1 \le N, M \le 2 \cdot 10^5;\ 1 \le K \le N)$; dòng hai gồm $x_1..x_N$; dòng ba gồm $p_1..p_M$; mọi tọa độ có giá trị tuyệt đối không quá $10^9$, có thể trùng nhau và không được sắp xếp.

Subtask:

• Subtask 1 (20%): $N, M \le 300$, tọa độ trong $[-300, 300]$.
• Subtask 2 (20%): $K = 1$.
• Subtask 3 (60%): không có ràng buộc gì thêm.

Input

5 4 2
1 5 9 14 20
3 8 12 18

Output

6

Giải thích

R = 6: cột 3 phủ [-3, 9],
cột 18 phủ [12, 24].
R = 5 thì cần 3 trạm.

Dành cho học viênNộp bài trên ClueOJ

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é. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Trạm phát sóng

Lời mở đầu

Bài kiểu "tìm giá trị nhỏ nhất sao cho điều kiện được thỏa" là dấu hiệu kinh điển của chặt nhị phân đáp án. Chỉ cần hai điều:

1. Tính đơn điệu: nếu bán kính $R$ phủ được hết nhà thì bán kính $R + 1$ cũng phủ được (giữ nguyên các cột đã chọn).
2. Hàm kiểm tra: với một $R$ cố định, trả lời nhanh "có cần không quá $K$ trạm không?".

Ví dụ của đề với $R = 6$ trông như thế này (chấm tím là nhà, tam giác là cột, cột đỏ là cột được chọn):

Hai trạm ở cột 3 và cột 18 phủ hết 5 ngôi nhà.

Cách 1Thử R tăng dần + QHĐ · 20%Cách 2K = 1: công thức · 20%Cách 3Chặt nhị phân + tham lam · 100%

Cách 1Thử $R = 0, 1, 2, \dots$ – O(R·N²·M) · 20%

Với tọa độ trong $[-300, 300]$ thì $R \le 600$. Thử lần lượt từng $R$; với mỗi $R$ dùng quy hoạch động $f[i]$ = số trạm ít nhất để phủ $i$ nhà đầu tiên (sau khi sắp xếp): từ trạng thái $i$, thử mọi cột phủ được nhà thứ $i$, nhảy tới nhà đầu tiên cột đó không phủ được.

#include <bits/stdc++.h>
using namespace std;
// Thu R = 0, 1, 2, ... ; voi moi R quy hoach dong f[i] = so cot it nhat phu i nha dau (O(N*M))
int main(){
    int n,m,K; cin>>n>>m>>K; vector<long long> x(n),p(m); for(auto&v:x)cin>>v; for(auto&v:p)cin>>v;
    sort(x.begin(),x.end());
    for(long long R=0;;R++){
        vector<int> f(n+1,INT_MAX/2); f[0]=0;
        for(int i=0;i<n;i++) if(f[i]<INT_MAX/2) for(int j=0;j<m;j++) if(llabs(p[j]-x[i])<=R){
            int k=i; while(k<n && llabs(p[j]-x[k])<=R) k++; f[k]=min(f[k],f[i]+1); }
        if(f[n]<=K){ cout<<R<<"\n"; return 0; }
    }
}

# Cach 1: thu R = 0, 1, 2, ...; moi R quy hoach dong f[i] = so tram it nhat phu i nha dau: 20%
n, m, K = map(int, input().split())
x = sorted(map(int, input().split()))
p = list(map(int, input().split()))
R = 0
while True:
    INF = 10**9
    f = [INF] * (n + 1); f[0] = 0
    for i in range(n):
        if f[i] == INF: continue
        for q in p:
            if abs(q - x[i]) <= R:
                k = i
                while k < n and abs(q - x[k]) <= R: k += 1
                f[k] = min(f[k], f[i] + 1)
    if f[n] <= K:
        print(R); break
    R += 1

Không gian$O(N)$

Thời gian$O(R \cdot N^2 \cdot M)$

Cách 2Khi $K = 1$ – O(N + M) · 20%

Chỉ có một trạm thì nó phải phủ cả nhà trái nhất $x_{\min}$ lẫn nhà phải nhất $x_{\max}$ (các nhà ở giữa tự khắc được phủ). Với mỗi cột $p$, bán kính cần là $\max(|p - x_{\min}|, |p - x_{\max}|)$; lấy nhỏ nhất trên mọi cột.

#include <bits/stdc++.h>
using namespace std;
int main(){ // K = 1: mot cot phai phu ca nha trai nhat va phai nhat
    int n,m,K; scanf("%d %d %d",&n,&m,&K); vector<long long> x(n),p(m); for(auto&v:x)scanf("%lld",&v); for(auto&v:p)scanf("%lld",&v);
    long long lo=*min_element(x.begin(),x.end()), hi=*max_element(x.begin(),x.end()), best=LLONG_MAX;
    for(auto q:p) best=min(best,max(llabs(q-lo),llabs(q-hi)));
    printf("%lld\n",best);
}

# Cach 2: K = 1 -> mot tram phai phu ca nha trai nhat va nha phai nhat: 20%
import sys
d = sys.stdin.buffer.read().split()
n, m, K = int(d[0]), int(d[1]), int(d[2])
x = list(map(int, d[3:3 + n])); p = list(map(int, d[3 + n:3 + n + m]))
lo, hi = min(x), max(x)
print(min(max(abs(q - lo), abs(q - hi)) for q in p))

Không gian$O(1)$

Thời gian$O(N + M)$

Cách 3Chặt nhị phân $R$ + kiểm tra tham lam – O((N + M) log N · log C) · 100%

Hàm kiểm tra ok(R) bằng tham lam

Sắp xếp nhà và cột. Lặp: lấy nhà trái nhất chưa có sóng $h$. Nhà này phải được một cột nào đó trong $[h - R, h + R]$ phủ. Trong các cột đó, chọn cột xa nhất về bên phải (cột lớn nhất $\le h + R$): mọi nhà bên trái $h$ đã có sóng rồi, nên chọn cột càng phải thì càng phủ được nhiều nhà phía sau. Đếm số trạm; vượt $K$ thì trả về false.

Tìm cột lớn nhất $\le h + R$ bằng upper_bound, rồi nhảy qua các nhà $\le p + R$ cũng bằng upper_bound. Mỗi trạm tốn $O(\log)$, nên một lần kiểm tra chỉ tốn $O(K \log N)$. Chặt nhị phân $R$ trong $[0, 4 \cdot 10^9]$ mất khoảng 32 lần kiểm tra.

Nhà Cột K

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, K; vector<ll> x, p;
bool ok(ll R){
    int i = 0, used = 0;
    while(i < n){
        ll h = x[i];
        int j = upper_bound(p.begin(), p.end(), h + R) - p.begin() - 1;   // cot xa nhat ve ben phai ma van phu duoc h
        if(j < 0 || p[j] < h - R) return false;
        if(++used > K) return false;
        ll cover = p[j] + R;
        i = upper_bound(x.begin(), x.end(), cover) - x.begin();
    }
    return true;
}
int main(){
    scanf("%d %d %d", &n, &m, &K);
    x.resize(n); p.resize(m);
    for(auto &v : x) scanf("%lld", &v);
    for(auto &v : p) scanf("%lld", &v);
    sort(x.begin(), x.end()); sort(p.begin(), p.end());
    ll lo = 0, hi = 4000000000LL;
    while(lo < hi){ ll mid = (lo + hi) / 2; if(ok(mid)) hi = mid; else lo = mid + 1; }
    printf("%lld\n", lo);
}

# Cach 3: chat nhi phan R + tham lam kiem tra - O((N + K) log N log C): 100%
import sys
from bisect import bisect_right
d = sys.stdin.buffer.read().split()
n, m, K = int(d[0]), int(d[1]), int(d[2])
x = sorted(map(int, d[3:3 + n])); p = sorted(map(int, d[3 + n:3 + n + m]))
def ok(R):
    i = used = 0
    while i < n:
        h = x[i]
        j = bisect_right(p, h + R) - 1          # cot xa nhat ben phai van phu duoc h
        if j < 0 or p[j] < h - R: return False
        used += 1
        if used > K: return False
        i = bisect_right(x, p[j] + R)
    return True
lo, hi = 0, 4 * 10**9
while lo < hi:
    mid = (lo + hi) // 2
    if ok(mid): hi = mid
    else: lo = mid + 1
print(lo)

Các bạn bấm chạy tay code C++ để xem từng dòng nhé (khá nhiều bước vì có cả chặt nhị phân, bấm "Tự chạy" chọn "Rất nhanh" cho đỡ mỏi tay):

C++▶ Chạy tay từng dòng codeCách 3: chặt nhị phân R, mỗi lần kiểm tra bằng tham lam "cột xa nhất bên phải".

Dữ liệu vào (stdin) – sửa thoải mái5 4 2 1 5 9 14 20 3 8 12 18

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4int n, m, K; vector<ll> x, p;

5bool ok(ll R){

6 int i = 0, used = 0;

7 while(i < n){

8 ll h = x[i];

9 int j = upper_bound(p.begin(), p.end(), h + R) - p.begin() - 1; // cot xa nhat ve ben phai ma van phu duoc h

10 if(j < 0 || p[j] < h - R) return false;

11 if(++used > K) return false;

12 ll cover = p[j] + R;

13 i = upper_bound(x.begin(), x.end(), cover) - x.begin();

14 }

15 return true;

16}

17int main(){

18 scanf("%d %d %d", &n, &m, &K);

19 x.resize(n); p.resize(m);

20 for(auto &v : x) scanf("%lld", &v);

21 for(auto &v : p) scanf("%lld", &v);

22 sort(x.begin(), x.end()); sort(p.begin(), p.end());

23 ll lo = 0, hi = 4000000000LL;

24 while(lo < hi){ ll mid = (lo + hi) / 2; if(ok(mid)) hi = mid; else lo = mid + 1; }

25 printf("%lld\n", lo);

26}

ChậmVừaNhanhRất nhanh

Không gian$O(N + M)$

Thời gian$O((N + M)\log + K \log N \log C)$

Hai cái bẫy trong bộ test

1. Chọn cột gần nhà $h$ nhất thay vì cột xa nhất bên phải: nghe hợp lý nhưng sai. Ví dụ nhà $0, 4$, cột $0, 1$, $K = 1$: đáp án đúng là $R = 3$ (cột $1$ phủ cả $[-2, 4]$). Nhưng với $R = 3$, cách "gần nhất" chọn cột $0$ cho nhà $0$, chỉ phủ tới $3$, bỏ sót nhà $4$ và kết luận phải tăng lên $R = 4$. Bộ test có nhiều trường hợp như vậy, code này sai ở cả 3 subtask.
2. Tràn số int: tọa độ tới $\pm 10^9$ nên đáp án có thể tới $2 \cdot 10^9$, và $h + R$ có thể tới $3 \cdot 10^9$ – vượt int. Có test chỉ có một cột ở $10^9$ với nhà ở $-10^9$.

Bộ test chấm "bắt" những lỗi nào?

Cách làm	Sub 1	Sub 2	Sub 3	Điểm
Cách 1 – thử R tăng dần	Đúng	TLE	TLE	20
Cách 2 – công thức K = 1	Sai	Đúng	Sai	20
Chặt nhị phân + chọn cột gần nhất	Sai	Sai	Sai	0
Chặt nhị phân + kiểm tra O(N·M)	Đúng	Đúng	TLE	40
Cách 3 nhưng dùng int	Đúng	Sai	Sai	20
Cách 3 với long long	Đúng	Đúng	Đúng	100

Ghi chú của mình: các code C++ đã được nộp thử trên ClueOJ với đúng bộ test của bài. Bản Python cách 3 cũng chạy đúng mọi test.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇