Xây Hàng Rào (HNOJ)

Nguồn: HNOJ (đọc/ghi file) Độ khó: Khá Tham lam Sắp xếp Cộng dồn

Đề bài

Marisa có $n$ tấm gỗ và sẽ sửa lại chúng để sử dụng, tấm gỗ thứ $i$ sẽ có độ đẹp là $A_i$ hoặc $B_i$ (tuỳ vào mục đích sử dụng mà Marisa sẽ sửa chúng khác nhau).

Marisa dự định chọn ra $k$ tấm gỗ để làm hàng rào bao quanh nhà. Trong đó, cô sẽ chọn ra $k - 1$ tấm để dựng hàng rào và 1 tấm để làm cửa. Khi đó, những tấm để làm hàng rào sẽ có độ đẹp là $A_i$ và tấm để làm cửa sẽ có độ đẹp là $B_i$.

Marisa đang cân nhắc số lượng tấm gỗ sử dụng để làm hàng rào, nên cô sẽ hỏi bạn $q$ câu hỏi, mỗi câu hỏi là một số nguyên $k$, hãy giúp cô tính độ đẹp lớn nhất có thể khi sử dụng $k$ tấm gỗ.

Dữ liệu vào từ tệp văn bản xayhangrao.inp:

• Dòng đầu tiên gồm hai số nguyên $n, q$.
• Dòng thứ hai gồm $n$ số nguyên $A_i$.
• Dòng thứ ba gồm $n$ số nguyên $B_i$.
• Dòng thứ tư gồm $q$ số nguyên $k$ theo thứ tự, mô tả các truy vấn.

Kết quả ghi ra tệp văn bản xayhangrao.out: In ra $q$ số nguyên, số nguyên thứ $i$ là đáp án truy vấn thứ $i$.

Giới hạn: Trong mọi test: $1 \le n, q \le 10^5$, $1 \le A_i, B_i \le 10^9$.

• Subtask 1 (25% số điểm): Marisa chỉ hỏi bạn một câu hỏi duy nhất với $k = n$.
• Subtask 2 (25% số điểm): $1 \le n, q \le 10$.
• Subtask 3 (25% số điểm): $1 \le n, q \le 1000$.
• Subtask 4 (25% số điểm): Không có giới hạn gì thêm.

Ví dụ: (khung trái là nội dung xayhangrao.inp, khung phải là nội dung xayhangrao.out)

Ví dụ 1 – input

3 1
3 5 4
5 8 5
3

Ví dụ 1 – output

15

Ví dụ 2 – input

3 2
3 5 4
5 8 5
3 2

Ví dụ 2 – output

15 12

Lưu ý về đọc/ghi file: các code bên dưới dùng mẹo if (fopen("xayhangrao.inp", "r")) { freopen(...); freopen(...); } (Python: if os.path.exists("xayhangrao.inp")): có file thì đọc/ghi file, không có thì đọc bàn phím và in ra màn hình. Nhờ vậy cùng 1 code nộp được cả lên hệ thống chấm đọc từ bàn phím lẫn khi thi chấm bằng file.

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 thêm đó là toàn bộ những gì mình đã trao đổi với em ấy để 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. Các bạn bấm vào link này để vào nộp bài nhé:

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

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 Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Hiểu đề1 tấm = 1 lựa chọnÝ tưởngTham lamCách 1O(Q·N) · 75%Cách 2Tính sẵn mọi k · 100%

Hiểu đềMỗi tấm gỗ chỉ là 1 lựa chọn

Đầu tiên giải thích đề bài nhé, sợ em chưa hiểu rõ. Bài đó tóm lại là thế này: $(A_i, B_i)$ là 1 thằng nhé, thì hãy chọn ra 1 thằng ở mảng $B$ và $k - 1$ thằng ở mảng $A$ sao cho tổng tụi nó là lớn nhất và các chỉ số index phân biệt nhau.

Ví dụ test 1 đề cho thì giải thích như sau (tính index từ 1 cho dễ nhé): khi $k = 3$, chọn thằng $B_2$ và $A_1$, $A_3$. Nên là: $8 + 3 + 4 = 15$.

	1	2	3
A (rào)	3	5	4
B (cửa)	5	8	5

k = 3: cửa B₂ = 8, rào A₁ = 3, A₃ = 4 → 15. Cột 2 đã làm cửa nên A₂ = 5 bị gạch.

Có bạn lại thắc mắc là:

HV

“Sao không chọn 8 + 5 + 4 mà lại chọn 8 + 3 + 4 ạ?”

Trả lời: Nếu chọn thằng 5 ở mảng $A$ thì đó là index 2, trong khi ta đã chọn index 2 ở mảng $B$ rồi mà em, không được trùng. Số 8 đã chọn là index 2 ở mảng $B$ rồi. Em hiểu không? Nếu đã chọn $B_2$ thì sẽ không được chọn $A_2$ và ngược lại.

HV

“e đọc e chỉ hiểu là ngta chọn ra k-1 tấm a và 1 tấm b chứ e không thấy nó phải né vị trí nhau”

Trả lời: Em đọc kỹ đề bài khúc đầu tiên nó có nói câu này: "tấm gỗ thứ $i$ sẽ có độ đẹp là $A_i$ hoặc $B_i$". Có nghĩa là $(A_i, B_i)$ là 1 lựa chọn. Ví dụ nếu chọn index 1 thì nó chỉ có thể là $A_1$ hoặc $B_1$ chứ không thể cùng cả 2, vì tụi nó chỉ là 1 tấm gỗ thôi.

Tương tự ví dụ 2: với $k = 2$ thì chọn cửa $B_2 = 8$ và 1 tấm rào lớn nhất còn lại là $A_3 = 4$ ⇒ $12$.

Ý tưởngTham lam + vét cạn trước

Bài này dùng tư tưởng tham lam (Greedy) để giải quyết. Kể cả bạn nào không biết về tư tưởng tham lam thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết.

Tham lam là gì?

Ta sẽ cố gắng chọn ra cách giải quyết tốt nhất trong tất cả các cách ở hiện tại rồi đi theo cách đó; nếu lại đứng trước nhiều lựa chọn khác nhau nữa thì ta lại cố gắng chọn cách tốt nhất trong số đó, tóm lại cứ tốt nhất mà triển, vì thế tên gọi nó là tham lam. Quy luật nó là như vậy thôi chứ không có công thức từng bước cụ thể như mấy thuật toán khác.

Anh nói em thế này: mọi bài nếu chưa nhìn ra thuật ăn full 100% của nó thì trước tiên hãy làm theo cách VÉT CẠN để ăn thử trước 1 số subtask và cũng để kiểm chứng ý tưởng đó có đúng không. Rồi khi thấy nó đúng rồi (tức là ăn hết được 1 số subtask nhỏ và bị TLE với các subtask lớn, tuyệt đối không có bị WA mà chỉ bị TLE) thì lúc này nhìn vào code vét cạn đó mà cải tiến lên để ăn full. Tất nhiên nói là vét cạn nhưng tư tưởng của nó cũng vẫn phải THAM LAM nha.

Gợi ý mấu chốt: chọn 1 phần tử ở mảng $B$ và $k - 1$ phần tử ở mảng $A$, thì $k$ có thể lớn lắm ($k \le n \le 10^5$), nhưng hãy nhìn lại mảng $B$ thì chỉ cần chọn 1 thằng thôi, chú ý kỹ nhé chỉ 1 thằng thôi. Đó là mấu chốt để nhìn ra ý tưởng vét cạn: mảng $B$ cần chọn 1 phần tử thì cứ giả sử chọn lần lượt từ $B_1$ đến $B_n$ thôi, rồi với mỗi lựa chọn đó sẽ chọn $k - 1$ phần tử lớn nhất còn lại trong mảng $A$ (khác index phần tử đã chọn của mảng $B$). Kết quả lớn nhất trong tất cả các cách chọn đó chính là đáp án.

Cách 1Sắp xếp + duyệt mỗi truy vấn – O(Q·N)

Đọc cặp số $(A_i, B_i)$ tương ứng là (first, second) em nhé, tức là ta có mảng pair hen. Sau đó sort tăng dần theo first. Ta sẽ bám theo yếu tố là ở second thì chỉ chọn duy nhất 1 tấm gỗ làm cửa, còn ở first thì chọn $k - 1$ tấm làm rào.

Tưởng tượng giờ nó đang tăng dần theo first, thì $k - 1$ thằng first cuối cùng sẽ có tổng lớn nhất tại vì tụi nó đang mang giá trị lớn nhất. Vậy:

• Trường hợp cửa nằm ngoài nhóm cuối: chọn $k - 1$ tấm first cuối cùng, thì để tham lam các thằng second từ đầu đến vị trí còn lại sẽ chọn thằng lớn nhất.
• Trường hợp cửa nằm trong nhóm cuối: lần lượt cho cửa là 1 trong các tấm cuối, khi đó tấm first ở vị trí đó bị bỏ ra và ta lấy thêm tấm first ngay phía trước nhóm.

Ví dụ nếu $n = 10$, $k = 3$ (số thứ tự tính từ 1 nhé), thì đầu tiên ta có: Max = a[10].first + a[9].first + max(a[1].second → a[8].second). Rồi giả sử chọn cửa là a[9].second thì để lớn nhất sẽ chọn a[10].first, a[8].first: Max = max(Max, a[9].second + a[10].first + a[8].first). Rồi chọn cửa là a[10].second thì chọn a[9].first, a[8].first: Max = max(Max, a[10].second + a[9].first + a[8].first). Lúc này đã xong, giá trị Max sau cùng là đáp án ứng với $k = 3$.

Anh liệt kê ra vài trường hợp $k = 2, 3, 4$ với $n = 10$ cho em xem, mỗi $k$ chọn Max của tất cả các dòng:

K = 2: Max của

max(a[1].second → a[9].second) + a[10].first

a[10].second + a[9].first

K = 3: Max của

max(a[1].second → a[8].second) + a[10].first + a[9].first

a[10].second + a[9].first + a[8].first

a[9].second + a[10].first + a[8].first

K = 4: Max của

max(a[1].second → a[7].second) + a[10].first + a[9].first + a[8].first

a[10].second + a[9].first + a[8].first + a[7].first

a[9].second + a[10].first + a[8].first + a[7].first

a[8].second + a[10].first + a[9].first + a[7].first

Thử tay cách chọn với từng k

Em nhập 2 dãy $A$, $B$ và số $k$ rồi bấm Tiếp: widget sẽ sắp xếp theo first, tô vàng các tấm làm rào, xanh tấm làm cửa (hoặc vùng lấy max second), rồi so sánh tất cả các trường hợp:

A (first) B (second) k

Ví dụ nhanh:

Với tư tưởng tham lam này dễ thấy với mỗi trường hợp $k$ ta sẽ xét qua hết $N$ phần tử là ra đáp án, và sẽ có $Q$ câu hỏi như vậy. Vậy cách làm vét cạn trước mắt sẽ có độ phức tạp $O(Q \cdot N)$, mà $Q, N$ tối đa $10^5$ nên $Q \cdot N = 10^{10}$, chắc chắn TLE vì đã vượt quá ngưỡng giới hạn 1 giây là $10^8$ rồi (vượt quá cả 100 lần). Nên chỉ ăn được 3 subtask đầu tiên, tức là 75% điểm:

• Subtask 1: $Q = 1$ ⇒ $O(Q \cdot N) = N$ mà $N$ tối đa $10^5$.
• Subtask 2: $N, Q \le 10$ ⇒ $10 \cdot 10 = 100$.
• Subtask 3: $N, Q \le 1000$ ⇒ $1000 \cdot 1000 = 10^6$.

Tất cả đều thỏa nhỏ hơn $10^8$ nên yên tâm cách làm có độ phức tạp $O(Q \cdot N)$ sẽ AC được 3 subtask đầu tiên. Đây là code theo cách này cho em tham khảo (trong code chỉ số tính từ 0, biến k được đổi thành n - k = vị trí tấm first "dự bị" ngay trước nhóm $k - 1$ tấm cuối):

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("xayhangrao.inp", "r")) {
        freopen("xayhangrao.inp", "r", stdin);
        freopen("xayhangrao.out", "w", stdout);
    }
    long long n, q;
    cin >> n >> q;
    vector<pair<long long, long long>> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i].first;
    }
    for(int i = 0; i < n; ++i){
        cin >> a[i].second;
    }
    sort(a.begin(), a.end());
    while(q--){
        long long k;
        cin >> k;
        k = n - k;
        long long sum = 0;
        for(int i = k + 1; i < n; ++i){
            sum += a[i].first;
        }
        long long Max = a[0].second;
        for(int i = 1; i <= k; ++i){
            Max = max(Max, a[i].second);
        }
        long long res = sum + Max;
        sum += a[k].first;
        for(int i = k + 1; i < n; ++i){
            res = max(res, sum + a[i].second - a[i].first);
        }
        cout << res << " ";
    }
    return 0;
}

import sys, os
if os.path.exists("xayhangrao.inp"):
    sys.stdin = open("xayhangrao.inp", "r")
    sys.stdout = open("xayhangrao.out", "w")
n, q = map(int, input().split())
a = []
first = list(map(int, input().split()))
second = list(map(int, input().split()))
for i in range(n):
    a.append((first[i], second[i]))
a.sort()
ks = list(map(int, input().split()))
for k in ks:
    k = n - k
    sum_ = 0
    for i in range(k + 1, n):
        sum_ += a[i][0]
    Max = a[0][1]
    for i in range(1, k + 1):
        Max = max(Max, a[i][1])
    res = sum_ + Max
    sum_ += a[k][0]
    for i in range(k + 1, n):
        res = max(res, sum_ + a[i][1] - a[i][0])
    print(res, end=' ')

C++▶ Chạy tay từng dòng codeCách 1: sort theo first, mỗi truy vấn duyệt N phần tử (TH1 + thử cửa trong nhóm cuối), O(Q·N).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 if (fopen("xayhangrao.inp", "r")) {

8 freopen("xayhangrao.inp", "r", stdin);

9 freopen("xayhangrao.out", "w", stdout);

10 }

11 long long n, q;

12 cin >> n >> q;

13 vector<pair<long long, long long>> a(n);

14 for(int i = 0; i < n; ++i){

15 cin >> a[i].first;

16 }

17 for(int i = 0; i < n; ++i){

18 cin >> a[i].second;

19 }

20 sort(a.begin(), a.end());

21 while(q--){

22 long long k;

23 cin >> k;

24 k = n - k;

25 long long sum = 0;

26 for(int i = k + 1; i < n; ++i){

27 sum += a[i].first;

28 }

29 long long Max = a[0].second;

30 for(int i = 1; i <= k; ++i){

31 Max = max(Max, a[i].second);

32 }

33 long long res = sum + Max;

34 sum += a[k].first;

35 for(int i = k + 1; i < n; ++i){

36 res = max(res, sum + a[i].second - a[i].first);

37 }

38 cout << res << " ";

39 }

40 return 0;

41}

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời gian$O(N \log N + Q \cdot N)$

Cách 2Tính sẵn đáp án mọi k – O(N log N + Q)

Còn để ăn được subtask cuối cùng thì em phải tìm cách tối ưu hơn. Nhận thấy rằng $N$ tối đa $10^5$ thì ta sẽ tính hết các trường hợp $k$ từ 1 đến $n$ trước. Vấn đề là chỗ này hãy nhìn kỹ nhé: không cần phải 2 vòng lặp lồng nhau vì nếu làm thế độ phức tạp sẽ là $O(N^2)$, mà chỗ này chỉ cần 1 vòng lặp duy nhất chạy từ 1 đến $n$ là tính ra được hết các đáp án. Để làm được điều đó em phải nhìn vào bản chất của các công thức. Anh viết lại công thức với $k = 2, 3, 4$ và $n = 10$ dưới dạng tổng sum, đánh dấu 3 màu: đỏ, cam, vàng:

Hình 1 · n = 10, sort tăng dần theo a.first

K = 2: Lấy Max của các thằng sau:

max(a[1].second → a[9].second) + sum(a[10].first → a[10].first)

sum(a[9].first → a[10].first) − a[10].first + a[10].second

K = 3: Lấy Max của các thằng sau:

max(a[1].second → a[8].second) + sum(a[9].first → a[10].first)

sum(a[8].first → a[10].first) − a[10].first + a[10].second

sum(a[8].first → a[10].first) − a[9].first + a[9].second

K = 4: Lấy Max của các thằng sau:

max(a[1].second → a[7].second) + sum(a[8].first → a[10].first)

sum(a[7].first → a[10].first) − a[10].first + a[10].second
sum(a[7].first → a[10].first) − a[9].first + a[9].second

sum(a[7].first → a[10].first) − a[8].first + a[8].second

Ở $k = 2$ thì chỉ có đỏ, cam, không có vàng; còn từ $k = 3$ trở lên là có đủ 3 màu. Em hãy nhìn những khối cùng màu trong các trường hợp $k$: ví dụ từ khối màu cam của $k = 2$ đi qua khối màu cam của $k = 3$ rồi đi qua khối màu cam của $k = 4$; từ khối màu vàng của $k = 3$ đi qua khối màu vàng của $k = 4$. Anh nghĩ em sẽ nhìn ra thứ gì đó 😉

Nhìn bằng hình: n = 10, k = 5

Khi $k = 5$ nghĩa là cần lấy 1 cái từ second và 4 cái từ first:

Hình 2 · k = 5, n = 10, first đang tăng dần

		1	2	3	4	5	6	7	8	9	10
TH1	first
	second	max các second tô xanh
TH2	first
	second
TH3	first
	second
TH4	first
	second
TH5	first
	second

• TH1: lấy 4 cái first to nhất (vì đang sắp tăng dần nên 4 thằng cuối cùng là 4 thằng to nhất), anh tô vàng đó; còn lại các thằng second được tô xanh thì lấy thằng có giá trị lớn nhất trong đó.
• TH2 → TH5: second lần lượt lấy vào các vị trí của 4 thằng tô vàng ở TH1. Khi second lấy vào vị trí thằng tô vàng nào thì thằng tô vàng đó sẽ dịch xuống 1 vị trí: TH2 second lấy vị trí 7 thì first ở vị trí 7 bỏ đi và ta lấy first ở vị trí 6; TH3 second lấy vị trí 8 thì bỏ first vị trí 8, lấy vị trí 6, 7…

Như thế em thấy từ TH2 trở đi, first luôn lấy tổng từ vị trí 6 đến 10, rồi trừ đi first ở vị trí cửa:

TH2 → TH5

TH2: sum(first a[6..10]) + a[7].second − a[7].first
TH3: sum(first a[6..10]) + a[8].second − a[8].first
TH4: sum(first a[6..10]) + a[9].second − a[9].first
TH5: sum(first a[6..10]) + a[10].second − a[10].first

Hai mảng tính sẵn

• Mảng MaxSecond: MaxSecond[i] = giá trị second lớn nhất của a[1], a[2], …, a[i] (lớn nhất từ đầu đến vị trí $i$) ⇒ chỉ cần $O(N)$ là tạo ra được.
• Mảng SumFirst: SumFirst[i] = tổng các giá trị first từ vị trí $i$ đến cuối mảng: a[i] + a[i+1] + … + a[n] ⇒ cũng chỉ $O(N)$.

Giờ nhìn lại "Hình 1":

• Màu đỏ: $k = 2$ là MaxSecond[9] + SumFirst[10]; $k = 3$ là MaxSecond[8] + SumFirst[9]; $k = 4$ là MaxSecond[7] + SumFirst[8]. Em có thấy cứ mỗi $k$ tăng lên 1 thì index của 2 thằng MaxSecond, SumFirst bị giảm đi 1 so với trước đó không? ⇒ tính trực tiếp $O(1)$.
• Màu cam: $k = 2$ là SumFirst[9] − a[10].first + a[10].second; $k = 3$ là SumFirst[8] − a[10].first + a[10].second, tức là chính trường hợp $k = 2$ nhưng cộng thêm a[8].first; $k = 4$ là trường hợp $k = 3$ cộng thêm a[7].first. Vậy max của cả khối cam chỉ cần lấy max cũ + first mới.
• Màu vàng: $k = 2$ không có, từ $k = 3$: SumFirst[8] − a[9].first + a[9].second; qua $k = 4$ thì là SumFirst[7] − a[8].first + a[8].second: nó chỉ lùi lại 1 index. Và khối vàng của $k$ này sẽ nhập vào khối cam của $k + 1$.

Đó, em nhìn ra những điểm tương đồng thì ở mỗi $k$ em tính ra Max của màu đỏ (Max1) và Max của màu cam + vàng (Max2). Khi đi qua $k$ tiếp theo thì dựa trên các biến Max của trường hợp trước đó mà sinh ra thêm cái mới rồi so sánh cập nhật lại ⇒ 1 vòng for chạy từ 1 đến N là đủ:

Công thức chuyển (chỉ số từ 0 như trong code)

Max1 = MaxSecond[n-k] + sumFirst[n-k+1]
Max2 = max(Max2 + a[n-k].first, sumFirst[n-k] - a[n-k+1].first + a[n-k+1].second)
ump[k] = max(Max1, Max2)

Rồi thì lưu các đáp án ứng với $k$ từ 1 đến $n$ đó lại (lúc hướng dẫn anh gợi ý dùng map hay unordered_map, nhưng vì key chính là $k$ từ 1 đến $n$ nên dùng luôn mảng vector ump là gọn và nhanh nhất), mỗi truy vấn chỉ việc in ump[k] trong $O(1)$:

• Bước input: $O(N)$.
• Bước sort: $O(N \log N)$.
• Bước xử lý: $O(\max(N, Q))$.

⇒ Tổng độ phức tạp của bài: $O(N \log N + Q)$. Đây là code của anh theo đúng ý tưởng đã nói, đã nộp AC trên web:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("xayhangrao.inp", "r")) {
        freopen("xayhangrao.inp", "r", stdin);
        freopen("xayhangrao.out", "w", stdout);
    }
    long long n, q;
    cin >> n >> q;
    vector<pair<long long, long long>> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i].first;
    }
    for(int i = 0; i < n; ++i){
        cin >> a[i].second;
    }
    sort(a.begin(), a.end());
    vector<long long> MaxSecond(n);
    MaxSecond[0] = a[0].second;
    for(int i = 1; i < n; ++i){
        MaxSecond[i] = max(MaxSecond[i - 1], a[i].second);
    }
    vector<long long> sumFirst(n);
    sumFirst[n - 1] = a[n - 1].first;
    for(int i = n - 2; i >= 0; --i){
        sumFirst[i] = sumFirst[i + 1] + a[i].first;
    }
    vector<long long> ump(n + 1);
    ump[1] = MaxSecond[n - 1];
    if(n >= 2){
        long long Max1 = MaxSecond[n - 2] + sumFirst[n - 1];
        long long Max2 = sumFirst[n - 2] - a[n - 1].first + a[n - 1].second;
        ump[2] = max(Max1, Max2);
        int j = 0;
        for(int k = 3; k <= n; ++k){
            j++;
            Max1 = MaxSecond[n - 2 - j] + sumFirst[n - 1 - j];
            Max2 = max(Max2 + a[n - k].first, sumFirst[n - k] - a[n - k + 1].first + a[n - k + 1].second);
            ump[k] = max(Max1, Max2);
        }
    }
    while(q--){
        long long x;
        cin >> x;
        cout << ump[x] << " ";
    }
    return 0;
}

import sys, os
if os.path.exists("xayhangrao.inp"):
    sys.stdin = open("xayhangrao.inp", "r")
    sys.stdout = open("xayhangrao.out", "w")
n, q = map(int, input().split())
first = list(map(int, input().split()))
second = list(map(int, input().split()))
a = [(first[i], second[i]) for i in range(n)]
a.sort()
MaxSecond = [0] * n
MaxSecond[0] = a[0][1]
for i in range(1, n):
    MaxSecond[i] = max(MaxSecond[i - 1], a[i][1])
sumFirst = [0] * n
sumFirst[-1] = a[-1][0]
for i in range(n - 2, -1, -1):
    sumFirst[i] = sumFirst[i + 1] + a[i][0]
ump = [0] * (n + 1)
ump[1] = MaxSecond[n - 1]
if n >= 2:
    Max1 = MaxSecond[n - 2] + sumFirst[n - 1]
    Max2 = sumFirst[n - 2] - a[n - 1][0] + a[n - 1][1]
    ump[2] = max(Max1, Max2)
    j = 0
    for k in range(3, n + 1):
        j += 1
        Max1 = MaxSecond[n - 2 - j] + sumFirst[n - 1 - j]
        Max2 = max(Max2 + a[n - k][0], sumFirst[n - k] - a[n - k + 1][0] + a[n - k + 1][1])
        ump[k] = max(Max1, Max2)
queries = list(map(int, input().split()))
for x in queries:
    print(ump[x], end=' ')

C++▶ Chạy tay từng dòng codeCách 2: tính sẵn MaxSecond, sumFirst rồi 1 vòng for ra ump[k] cho mọi k, mỗi truy vấn O(1).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 if (fopen("xayhangrao.inp", "r")) {

8 freopen("xayhangrao.inp", "r", stdin);

9 freopen("xayhangrao.out", "w", stdout);

10 }

11 long long n, q;

12 cin >> n >> q;

13 vector<pair<long long, long long>> a(n);

14 for(int i = 0; i < n; ++i){

15 cin >> a[i].first;

16 }

17 for(int i = 0; i < n; ++i){

18 cin >> a[i].second;

19 }

20 sort(a.begin(), a.end());

21 vector<long long> MaxSecond(n);

22 MaxSecond[0] = a[0].second;

23 for(int i = 1; i < n; ++i){

24 MaxSecond[i] = max(MaxSecond[i - 1], a[i].second);

25 }

26 vector<long long> sumFirst(n);

27 sumFirst[n - 1] = a[n - 1].first;

28 for(int i = n - 2; i >= 0; --i){

29 sumFirst[i] = sumFirst[i + 1] + a[i].first;

30 }

31 vector<long long> ump(n + 1);

32 ump[1] = MaxSecond[n - 1];

33 if(n >= 2){

34 long long Max1 = MaxSecond[n - 2] + sumFirst[n - 1];

35 long long Max2 = sumFirst[n - 2] - a[n - 1].first + a[n - 1].second;

36 ump[2] = max(Max1, Max2);

37 int j = 0;

38 for(int k = 3; k <= n; ++k){

39 j++;

40 Max1 = MaxSecond[n - 2 - j] + sumFirst[n - 1 - j];

41 Max2 = max(Max2 + a[n - k].first, sumFirst[n - k] - a[n - k + 1].first + a[n - k + 1].second);

42 ump[k] = max(Max1, Max2);

43 }

44 }

45 while(q--){

46 long long x;

47 cin >> x;

48 cout << ump[x] << " ";

49 }

50 return 0;

51}

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

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

Ghi chú của mình: code C++ và Python của cả 2 cách là của anh, mình chỉ thêm mẹo fopen / os.path.exists để đọc/ghi file. Cả 4 bản đã được kiểm tra với 300 bộ test ngẫu nhiên ($n, q \le 8$, giá trị nhỏ nhiều số trùng lẫn giá trị tới $10^9$) so với code vét cạn thử mọi tấm làm cửa rồi lấy $k - 1$ tấm rào lớn nhất còn lại: khớp 100%. Với $n = q = 10^5$: cách 2 bản C++ chạy khoảng 0.06 giây, bản Python khoảng 0.9 giây; cách 1 bản C++ chạy hơn 10 giây ⇒ TLE subtask 4 đúng như phân tích (với $n = q = 1000$ chỉ mất vài mili giây).

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 😇

Khuyến Mãi (mua bút)

Nguồn: Codeforces Group Độ khó: Dễ Toán học Chia lấy dư

Đề bài

Nhân dịp khai trương, siêu thị Big C tổ chức bán bút với chương trình khuyến mãi như sau: Giá một chiếc bút là $t$ đồng, khi mua $m$ chiếc khách hàng được tặng thêm 1 chiếc. Để phục vụ kỳ thi, Ban tổ chức cần phải chuẩn bị ít nhất $n$ bút phát cho các thí sinh dự thi.

Yêu cầu: Cho biết $m$, $n$ và $t$. Tính số tiền $S$ (đơn vị đồng) ít nhất cần có để mua bút.

Dữ liệu nhập:

• Gồm một dòng chứa ba số nguyên dương $m$, $n$ và $t$ $(1 \le m \le 10^9,\ 0 \le n, t \le 10^9)$, mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất: Là một số nguyên xác định số tiền cần thiết.

Thang điểm:

• 50% số test đầu tiên có $m, n, t \le 10^6$.
• 50% số test còn lại không có giới hạn gì thêm.

Ví dụ – input

2 3 100

Ví dụ – output

200

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

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 Codeforces

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Cần mua $n = 3$ bút, cửa hàng khuyến mãi mua $m = 2$ bút được tặng 1 bút, giá mỗi bút là $t = 100$. Vậy trong tình huống này ta sẽ mua 2 bút và được tặng 1 bút, như thế sẽ được $2 + 1 = 3$ bút là bằng với số lượng cần. 2 bút mua thì tiền $= 2 \times 100 = 200$ nên đáp án là 200 nha các bạn.

mua (trả tiền) được tặng → mua 2 cây × 100 = 200

Bài này mình sẽ giải theo 2 cách: cách đầu "không cần nặng đầu suy nghĩ" ăn được 50% điểm, cách sau làm nháp 1 tí là ra công thức $O(1)$ ăn full.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vòng lặp O(N) · 50%Cách 2Công thức O(1) · 100%

Cách 1Mô phỏng từng lần mua – O(N)

Một cách cực kỳ đơn giản không cần phải nặng đầu suy nghĩ đó là chúng ta cứ cho vòng lặp for i chạy từ 1 đến $n$ (là số bút cần mua). Ta tạo biến cnt để mỗi lần mua 1 bút thì sẽ tăng biến cnt lên (cnt++).

Vấn đề là cứ mua đủ $m$ bút thì được tặng 1 bút. Vậy nên trong quá trình lặp ta kiểm tra nếu tại lần mua nào mà $i$ chia hết cho $m$ (i % m == 0) tức là tại lần đó sẽ được tặng thêm 1 bút, thì ngay lúc đó sẽ giảm số bút cần mua đi 1 đơn vị (n--) bởi vì đã được tặng 1 bút rồi. Sau cùng đáp án sẽ là cnt * t (số lượng × giá tiền).

Vì sao n-- lại đúng?

Biến $n$ ở đây đóng vai trò "số bút còn phải mua". Mỗi lần được tặng 1 cây thì cái đích $n$ lùi lại 1 bước, nên vòng lặp dừng sớm hơn. Ví dụ $m = 2, n = 5$: mua cây 1; mua cây 2 (chia hết cho 2 → được tặng, $n$ còn 4); mua cây 3; mua cây 4 (được tặng, $n$ còn 3); tới $i = 5 > n = 3$ thì dừng. Vậy chỉ trả tiền 4 cây, được tặng 2 cây, có $6 \ge 5$ cây. Em bấm dữ liệu m = 2, n = 5 trong khung chạy tay bên dưới để xem từng bước nhé.

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

#include <iostream>
using namespace std;

int main(){
    long long m, n, t, cnt = 0;
    cin >> m >> n >> t;
    for(int i = 1; i <= n; ++i){
        if(i % m == 0){
            n--;
        }
        cnt++;
    }
    cout << t * cnt;
    return 0;
}

m, n, t = map(int, input().split())
cnt = 0
i = 1
while i <= n:
    if i % m == 0:
        n -= 1
    cnt += 1
    i += 1
print(t * cnt)

C++▶ Chạy tay từng dòng codeCách 1: mua từng cây, cứ i chia hết cho m thì n-- (được tặng), O(N).

Dữ liệu vào (stdin) – sửa thoải mái2 3 100

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long m, n, t, cnt = 0;

6 cin >> m >> n >> t;

7 for(int i = 1; i <= n; ++i){

8 if(i % m == 0){

9 n--;

10 }

11 cnt++;

12 }

13 cout << t * cnt;

14 return 0;

15}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$ do trong bài này chỉ dùng các biến đơn lẻ, không dùng mảng gì để lưu trữ cả.
• Thời gian: Ta thấy vòng lặp chạy từ 1 đến $N$, tức là lặp $N$ lần. Tuy nhiên thực tế số lần lặp có thể ít hơn vì khi gặp giá trị $i$ chia hết cho $m$ thì $N$ bị giảm đi 1 đơn vị. Nhưng trong tình huống xấu nhất nếu $M \ge N$ (đề bài không quy định $M < N$ nên tình huống này vẫn có thể xảy ra) thì vòng lặp sẽ vẫn phải chạy đủ $N$ lần. Vì thế ta có thể kết luận độ phức tạp thời gian sẽ là $O(N)$ nha các bạn.

Không gian$O(1)$

Thời gian$O(N)$

Chỉ được 50% điểm

Với $O(N)$ thì sẽ chỉ lấy được subtask 1 với 50% điểm khi $n$ tối đa $10^6$. Còn subtask 2 với $n$ tối đa $10^9$ thì chắc chắn sẽ bị TLE. Mình sẽ hướng dẫn cho các bạn một cách làm tối ưu hơn cả về hiệu suất chạy lẫn số lượng dòng phải code để có thể full điểm, chỉ là phải chịu khó làm nháp 1 tí thôi, các bạn xem nhé.

Cách 2Làm nháp ra công thức – O(1)

Mua $M$ bút được tặng thêm 1 bút ⇒ cả thảy có: $M + 1$ bút.

Vậy ta sẽ hiểu nếu được tặng 2 lần, tức là số bút cả thảy có: $2M + 2$. Tương tự sẽ tiếp tục là: $3M + 3$, $4M + 4$, …

Tổng quát sẽ là: $X \cdot M + X$ nếu ta được tặng $X$ lần (đồng nghĩa số bút phải mua là $X \cdot M$).

Và ta đâu cần mua dư nhiều làm gì, chỉ cần làm sao để tổng sau cùng số bút sẽ bằng $N$ thôi (hoặc vượt hơn cũng được nhưng không được ít hơn), tức là ta có:

Làm nháp

$X \cdot M + X$ $\ge N \iff X \cdot (M + 1)$ $\ge N \iff X$ $\ge \dfrac{N}{M + 1}$

Tìm ra giá trị $X$ rồi thì ta sẽ thế vào tính ra số bút cần mua chính là $X \cdot M$, từ đó tính ra giá tiền.

Thử với ví dụ M = 6, N = 15, T = 1000

Ta sẽ tính $\dfrac{N}{M + 1}$ $= \dfrac{15}{6 + 1}$ $= \dfrac{15}{7}$ $\approx 2.14$. Tức là $X \ge 2.14$.

• Nếu giả sử lúc này ta chọn $X = 3$ thì số bút cần mua sẽ là $X \cdot M = 3 \cdot 6 = 18$ bút và được tặng thêm $X = 3$ bút ⇒ tổng số bút có được sẽ là $18 + 3 = 21$, đã vượt quá chỉ tiêu cần mua là 15. Nếu tính tiền thì $18 \times 1000 = 18\,000$ phải trả.
• Nếu giả sử chọn $X = 2$ thì số bút cần mua sẽ là $X \cdot M = 2 \cdot 6 = 12$ và được tặng thêm $X = 2$ bút ⇒ tổng số bút có được sẽ là $12 + 2 = 14$. Lúc này còn thiếu 1 bút so với chỉ tiêu ⇒ số bút cần mua sẽ là $12 + 1 = 13$ bút và tính tiền thì $13 \times 1000 = 13\,000$ phải trả.

Vậy đáp án số tiền ít nhất để mua đủ $N = 15$ bút sẽ là 13 000.

M = 6, N = 15: 2 nhóm đủ 7 cây + 1 cây lẻ

X = 2 nhóm (mỗi nhóm trả 6 cây), Y = 1 cây lẻ → trả tiền 2·6 + 1 = 13 cây = 13 000 đồng

Vậy ta thấy công thức là sao các bạn? Chia $N$ bút thành các nhóm $M + 1$ cây (mỗi nhóm trả tiền $M$ cây, cây còn lại được tặng), phần lẻ không đủ 1 nhóm thì phải mua hết:

Công thức

$X = \left\lfloor \dfrac{N}{M + 1} \right\rfloor$ (phép chia lấy phần nguyên), $\ Y = N \bmod (M + 1)$, $\ S = (X \cdot M + Y) \cdot T$.

Như ví dụ trên $X = 15 / 7 = 2$ (phép chia lấy phần nguyên) và $Y = 15 \bmod 7 = 1$. Đáp án sẽ là: $(2 \cdot 6 + 1) \cdot 1000 = 13\,000$.

Thử kiểm chứng công thức trong 1 trường hợp đặc biệt khác, khi $M \ge N$. Ví dụ $M = 100, N = 5, T = 1000$. Rõ ràng ta thấy phải mua 100 bút mới được tặng 1 bút, mà ta chỉ cần $N = 5$ bút thôi nên coi như mua đúng 5 bút và không được tặng gì hết ⇒ số tiền phải trả $= 5 \times 1000 = 5\,000$. Áp dụng công thức: $X = 5 / 101 = 0$, $Y = 5 \bmod 101 = 5$. Đáp án sẽ là: $(0 \cdot 100 + 5) \cdot 1000 = 5\,000$. Chuẩn luôn 😎

Minh hoạ chia nhóm

Em nhập $m$, $n$, $t$ rồi bấm Tiếp để xem từng nhóm $m + 1$ cây được "gom" như thế nào (cây xanh = trả tiền, cây vàng = được tặng):

m n t

Ví dụ nhanh:

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

#include <iostream>
using namespace std;

int main(){
    long long m, n, t;
    cin >> m >> n >> t;
    long long x = n / (m + 1);
    long long y = n % (m + 1);
    cout << (x * m + y) * t;
    return 0;
}

m, n, t = map(int, input().split())
x = n // (m + 1)
y = n % (m + 1)
print((x * m + y) * t)

C++▶ Chạy tay từng dòng codeCách 2: chia n thành các nhóm m + 1 cây, S = (x·m + y)·t, O(1).

Dữ liệu vào (stdin) – sửa thoải mái6 15 1000

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 long long m, n, t;

6 cin >> m >> n >> t;

7 long long x = n / (m + 1);

8 long long y = n % (m + 1);

9 cout << (x * m + y) * t;

10 return 0;

11}

ChậmVừaNhanhRất nhanh

Lúc này đây độ phức tạp về không gian và thời gian đều là $O(1)$ hết và đây là cách làm tối ưu nhất nha các bạn, không có cách nào tối ưu hơn. Và so với code của cách trước đó thì còn gọn hơn rất nhiều, phần xử lý chỉ cần 3 dòng, thậm chí bạn nào thích chơi gộp có thể gộp lại làm 1 dòng duy nhất: cout << ((n / (m + 1)) * m + (n % (m + 1))) * t;

Không gian$O(1)$

Thời gian$O(1)$

Nhớ dùng long long

Đáp án có thể lên tới cỡ $10^9 \times 10^9 = 10^{18}$ (ví dụ $m = 10^9$, $n = t = 10^9$ thì phải mua đủ $10^9$ cây), vượt xa int. Vì thế code dùng long long cho tất cả các biến (vẫn còn vừa vì long long chứa được tới khoảng $9.2 \cdot 10^{18}$).

Ghi chú của mình: code C++ và Python của cả 2 cách là của anh (mình chỉ sửa lại thụt lề). Cả 4 bản đã được kiểm tra với 300 bộ test ngẫu nhiên, so với code vét cạn "tăng dần số bút mua $b$ cho tới khi $b + \lfloor b/m \rfloor \ge n$" – khớp hết. Với $m = n = t = 10^9$: cách 1 (C++) chạy hơn 10 giây ⇒ TLE đúng như phân tích, còn cách 2 chạy tức thì (dưới 0.01 giây).

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 😇