Sửa đồng hồ (Đề tự luyện HSG Tin 9 – Bài 2) – Tham lam bằng kĩ thuật đổi chỗ hai việc kề nhau

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 2 (đề tự soạn) Độ khó: Trung bình Tham lam Sắp xếp Đổi chỗ hai phần tử kề nhau

Đề bài

Sửa đồng hồ

Sáng nay tiệm của thầy Sơn nhận cùng lúc $N$ chiếc đồng hồ (tất cả giao ở thời điểm $0$). Chiếc thứ $i$ cần đúng $t_i$ phút để sửa. Thầy Sơn chỉ sửa được một chiếc tại một thời điểm, đã bắt đầu chiếc nào thì phải sửa xong chiếc đó mới chuyển sang chiếc khác, giữa hai chiếc không nghỉ.

Khách thứ $i$ được đền $w_i$ nghìn đồng cho mỗi phút chờ: nếu đồng hồ $i$ xong tại thời điểm $C_i$ thì tiệm đền $w_i \times C_i$. Hãy chọn thứ tự sửa để tổng tiền đền $\sum w_i \times C_i$ nhỏ nhất.

Dữ liệu vào: Dòng đầu là $N$ $(1 \le N \le 2 \cdot 10^5)$. $N$ dòng sau, dòng $i$ gồm $t_i$ và $w_i$ $(1 \le t_i, w_i \le 10^4)$.

Kết quả: Tổng tiền đền bù nhỏ nhất.

Subtask:

• Subtask 1 (20%): $N \le 8$.
• Subtask 2 (30%): $w_i = 1$ với mọi $i$.
• Subtask 3 (50%): không có ràng buộc gì thêm.

Input

3
3 1
1 2
4 6

Output

40

Giải thích

Thứ tự 2 → 3 → 1:
2·1 + 6·5 + 1·8 = 40

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 Sửa đồng hồ

Lời mở đầu

Đây là một bài tham lam rất "đánh lừa": có tới mấy cách tham lam nghe đều hợp lý, nhưng chỉ có một cách đúng. Thử với ví dụ của đề, ta so sánh vài thứ tự:

Ba "luật" tham lam cho ba kết quả khác nhau: 54, 42 và 40. Chỉ luật thứ ba ra đáp án đúng.

• Việc ngắn làm trước (t tăng dần): bỏ qua chuyện khách $3$ có $w = 6$ rất "đắt", để khách đó chờ lâu ⇒ $54$.
• Khách đắt làm trước (w giảm dần): bỏ qua chuyện việc đó dài, khiến người khác chờ ⇒ $42$.
• Cần một tiêu chí kết hợp cả t và w. Phần Cách 3 sẽ chứng minh tiêu chí đó là $t/w$.

Cách 1Thử mọi hoán vị · 20%Cách 2w = 1: việc ngắn trước · 30%Cách 3Sắp theo t/w · 100%

Cách 1Thử tất cả các thứ tự – O(N!·N) · 20%

Với $N \le 8$ chỉ có $8! = 40320$ thứ tự. Ta dùng next_permutation sinh lần lượt từng hoán vị, tính tổng tiền đền của mỗi thứ tự và lấy nhỏ nhất.

#include <bits/stdc++.h>
using namespace std;

// Cach 1: thu het N! thu tu - O(N! * N): 20%
int main(){
    int n;
    cin >> n;
    vector<long long> t(n), w(n);
    for(int i = 0; i < n; i++) cin >> t[i] >> w[i];
    vector<int> p(n);
    for(int i = 0; i < n; i++) p[i] = i;
    long long best = LLONG_MAX;
    do{
        long long cur = 0, sum = 0;
        for(int i : p){
            cur += t[i];          // thoi diem sua xong dong ho i
            sum += w[i] * cur;
        }
        best = min(best, sum);
    } while(next_permutation(p.begin(), p.end()));
    cout << best;
    return 0;
}

# Cach 1: thu het N! thu tu - O(N! * N): 20%
from itertools import permutations
n = int(input())
t = []; w = []
for _ in range(n):
    a, b = map(int, input().split())
    t.append(a); w.append(b)
best = None
for p in permutations(range(n)):
    cur = 0; s = 0
    for i in p:
        cur += t[i]
        s += w[i] * cur
    if best is None or s < best:
        best = s
print(best)

• Thời gian: $O(N! \cdot N)$ – với $N = 8$ là khoảng $3 \cdot 10^5$ phép tính. Nhưng $N = 12$ đã là $5.7 \cdot 10^9$, còn $N = 2 \cdot 10^5$ thì khỏi nghĩ 😅.

Không gian$O(N)$

Thời gian$O(N! \cdot N)$

Cách 2Khi mọi $w_i = 1$: việc ngắn làm trước – O(N log N) · 30%

Khi $w_i = 1$, tổng cần tối thiểu là $C_1 + C_2 + \dots + C_N$. Nếu sửa theo thứ tự $p_1, p_2, \dots, p_N$ thì việc $p_1$ được cộng vào thời điểm xong của tất cả $N$ chiếc, việc $p_2$ được cộng $N - 1$ lần, …:

$$\sum C = N \cdot t_{p_1} + (N-1) \cdot t_{p_2} + \dots + 1 \cdot t_{p_N}$$

Hệ số lớn nhất phải nhân với $t$ nhỏ nhất ⇒ sắp xếp $t$ tăng dần. Đây cũng là lý do luật "việc ngắn trước" đúng cho subtask 2 – nhưng sai khi $w$ khác nhau như đã thấy ở trên.

#include <bits/stdc++.h>
using namespace std;

// Cach 2: w deu bang 1 -> lam viec ngan truoc - O(N log N): 30%
int main(){
    int n;
    cin >> n;
    vector<long long> t(n), w(n);
    for(int i = 0; i < n; i++) cin >> t[i] >> w[i];
    sort(t.begin(), t.end());
    long long cur = 0, ans = 0;
    for(int i = 0; i < n; i++){
        cur += t[i];
        ans += cur;        // w = 1
    }
    cout << ans;
    return 0;
}

# Cach 2: w deu bang 1 -> lam viec ngan truoc - O(N log N): 30%
import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
t = sorted(int(data[1 + 2 * i]) for i in range(n))
cur = 0; ans = 0
for x in t:
    cur += x
    ans += cur
print(ans)

Không gian$O(N)$

Thời gian$O(N \log N)$

Cách 3Sắp xếp theo $t_i / w_i$ tăng dần – O(N log N) · 100%

Kĩ thuật chứng minh tham lam kinh điển: xét hai việc đứng cạnh nhau $i$ rồi $j$ trong một thứ tự bất kỳ, và hỏi: đổi chỗ chúng thì tổng tăng hay giảm?

Các việc ở phần trước và phần sau có thời điểm xong không đổi (tổng thời gian của $i$ và $j$ vẫn là $t_i + t_j$). Chỉ có $i$ và $j$ thay đổi:

• Nếu $i$ đứng trước: $j$ phải chờ thêm $t_i$ phút ⇒ phần chênh là $w_j \cdot t_i$.
• Nếu $j$ đứng trước: $i$ phải chờ thêm $t_j$ phút ⇒ phần chênh là $w_i \cdot t_j$.

Kết luận

$i$ nên đứng trước $j$ khi $t_i \cdot w_j < t_j \cdot w_i \iff \dfrac{t_i}{w_i} < \dfrac{t_j}{w_j}$. Một thứ tự mà còn hai việc kề nhau "ngược" tiêu chí này thì đổi chỗ chúng sẽ làm tổng giảm (hoặc giữ nguyên), nên thứ tự tối ưu chính là sắp xếp theo $t/w$ tăng dần.

Ý nghĩa thực tế: $t/w$ là "số phút sửa cho mỗi đồng tiền phạt" – việc nào vừa nhanh vừa đắt thì làm trước. Các bạn đổi quy tắc ở khung dưới để thấy các luật khác thua thế nào:

Danh sách t w Quy tắc t/w tăng dầnt tăng dầnw giảm dầnthứ tự nhập

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;

// Cach 3: sap xep theo t/w tang dan (so sanh nhan cheo) - O(N log N): 100%
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> t(n), w(n);
    for(int i = 0; i < n; i++) cin >> t[i] >> w[i];
    vector<int> id(n);
    for(int i = 0; i < n; i++) id[i] = i;
    // i dung truoc j neu t[i]/w[i] < t[j]/w[j]  <=>  t[i]*w[j] < t[j]*w[i]
    sort(id.begin(), id.end(), [&](int i, int j){
        return t[i] * w[j] < t[j] * w[i];
    });
    long long cur = 0, ans = 0;
    for(int i : id){
        cur += t[i];
        ans += w[i] * cur;
    }
    cout << ans;
    return 0;
}

# Cach 3: sap xep theo t/w tang dan - O(N log N): 100%
import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
jobs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]
jobs.sort(key=lambda x: x[0] / x[1])   # t, w <= 10^4 nen so thuc du chinh xac
cur = 0; ans = 0
for t, w in jobs:
    cur += t
    ans += w * cur
print(ans)

Các bạn bấm chạy tay code C++ để xem từng dòng nhé:

C++▶ Chạy tay từng dòng codeCách 3: sắp xếp chỉ số theo t·w chéo, rồi cộng dồn thời điểm xong.

Dữ liệu vào (stdin) – sửa thoải mái3 3 1 1 2 4 6

Dữ liệu mẫu:

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

2using namespace std;

3

4// Cach 3: sap xep theo t/w tang dan (so sanh nhan cheo) - O(N log N): 100%

5int main(){

6 ios::sync_with_stdio(false); cin.tie(nullptr);

7 int n;

8 cin >> n;

9 vector<long long> t(n), w(n);

10 for(int i = 0; i < n; i++) cin >> t[i] >> w[i];

11 vector<int> id(n);

12 for(int i = 0; i < n; i++) id[i] = i;

13 // i dung truoc j neu t[i]/w[i] < t[j]/w[j] <=> t[i]*w[j] < t[j]*w[i]

14 sort(id.begin(), id.end(), [&](int i, int j){

15 return t[i] * w[j] < t[j] * w[i];

16 });

17 long long cur = 0, ans = 0;

18 for(int i : id){

19 cur += t[i];

20 ans += w[i] * cur;

21 }

22 cout << ans;

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời gian$O(N \log N)$

Đáp án rất lớn – phải dùng long long

Tổng thời gian tối đa $2 \cdot 10^5 \cdot 10^4 = 2 \cdot 10^9$ (đã vượt int), còn tổng tiền đền có thể tới khoảng $2 \cdot 10^{18}$ (có test đúng bằng $2000010000000000000$). long long chứa được tới $9.2 \cdot 10^{18}$ nên vẫn vừa – nhưng chỉ cần một biến int là sai.

So sánh bằng nhân chéo thay vì chia

Viết t[i] * w[j] < t[j] * w[i] thì hoàn toàn là số nguyên (tối đa $10^8$), không sợ sai số làm tròn. Bản Python dùng t / w vẫn an toàn vì với $t, w \le 10^4$ hai tỉ số khác nhau thì chênh nhau ít nhất $10^{-8}$, lớn hơn rất nhiều so với sai số của số thực. Những việc có tỉ số bằng nhau thì đứng theo thứ tự nào cũng cho cùng một tổng.

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ử hoán vị	Đúng	TLE	TLE	20
Cách 2 – t tăng dần	Sai	Đúng	Sai	30
w giảm dần / t − w tăng dần	Sai	Đúng*	Sai	30
Đúng ý tưởng nhưng chọn việc O(N²)	Đúng	TLE	TLE	20
Đúng ý tưởng nhưng biến tổng kiểu int	Đúng	Đúng	Sai	50
Cách 3 với long long	Đúng	Đúng	Đúng	100

(*) khi mọi $w = 1$ thì các luật này trở thành "t tăng dần" nên vẫn đúng ở subtask 2.

Ghi chú của mình: cả 3 cách C++ đã được nộp thử trên ClueOJ với đúng bộ test của bài: cách 1 được 20 điểm, cách 2 được 30 điểm, cách 3 được 100 điểm. Bản Python của cách 3 cũng chạy đúng với 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 😇