Các Hiệp Sĩ (GREKNIGHT)
Đề bài
GREKNIGHT – Các hiệp sĩ
Khác với Hiệp sĩ thành Tron, Hiệp sĩ Ba Lan tước đi sự quý phái và hạnh phúc khi giao đấu với nhau. Mỗi hiệp sĩ có một chỉ số sức mạnh và chiến thắng một hiệp sĩ khác khi và chỉ khi sức mạnh của anh ta lớn hơn sức mạnh của đối phương.
Tuy nhiên theo quy định của quốc vương thì mỗi hiệp sĩ được giao đấu với không quá $k$ hiệp sĩ khác. Ngoài ra, mỗi hiệp sĩ có một số lượng tiền. Sau khi chiến thắng đối thủ, một hiệp sĩ có thể giành được tiền thưởng là số tiền của đối thủ.
Bây giờ mỗi hiệp sĩ suy ngẫm: anh ta có thể có bao nhiêu tiền nếu giao đấu với các hiệp sĩ khác. Bạn nên trả lời câu hỏi này cho mỗi hiệp sĩ.
Dữ liệu nhập:
- Dòng đầu tiên chứa hai số nguyên $n$ và $k$ $(1 \le n \le 10^5,\ 0 \le k \le \min(n - 1, 10))$ – số hiệp sĩ và số $k$.
- Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \ldots, p_n$ $(1 \le p_i \le 10^9)$ – sức mạnh của các hiệp sĩ. Sức mạnh của $n$ hiệp sĩ khác nhau từng đôi một.
- Dòng thứ ba chứa $n$ số nguyên $c_1, c_2, \ldots, c_n$ $(0 \le c_i \le 10^9)$ – số lượng tiền mỗi hiệp sĩ có.
Kết quả:
- In $n$ số nguyên – số tiền tối đa mà mỗi hiệp sĩ có thể có nếu anh ta giao đấu với tối đa $k$ hiệp sĩ khác.
Giới hạn thời gian: 1.0 giây. Giới hạn bộ nhớ: 128 megabyte.
4 2
4 5 9 7
1 2 11 331 3 46 365 1
1 2 3 4 5
1 2 3 4 51 3 5 7 91 0
2
33Lờ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ài này cũng chính là bài Knights of a Polygonal Table – Codeforces 994B, bạn nào quen Codeforces có thể tìm thêm.)
Ngoài ra một thử thách mình đặt thêm với em học viên: kể cả đã AC rồi thì hãy tối ưu code sao cho thời gian chạy trên web $\le 125$ ms (lúc mình viết bài, nhanh nhất trên bảng chấm là 125 ms, rồi có bạn còn AC với 109 ms nữa hehe 😆).
Nhắc lại: với giới hạn 1 giây, toàn bài chỉ nên lặp khoảng $(3 \to 5) \cdot 10^7$ lần là an toàn, tệ nhất $10^8$ (hên xui). Ngưỡng này là cho C/C++, Python chậm hơn nên ngưỡng còn thấp hơn.
Đọc kỹ đề: mỗi hiệp sĩ được đấu với tối đa $k$ hiệp sĩ khác (có thể ít hơn, nhưng $k + 1$ trở lên là không được). Hiệp sĩ mạnh hơn thì thắng và lấy hết tiền của đối thủ – giống như cá cược vậy đó. Câu hỏi được hỏi độc lập cho từng hiệp sĩ.
Giải thích ví dụ 1 ($n = 4$, $k = 2$):
- Hiệp sĩ 1 (sức mạnh 4, tiền 1): không ai yếu hơn ⇒ không đấu được với ai ⇒ 1.
- Hiệp sĩ 2 (sức mạnh 5, tiền 2): chỉ hiệp sĩ 1 yếu hơn, $1 \le k$ nên đấu luôn ⇒ $2 + 1 =$ 3.
- Hiệp sĩ 3 (sức mạnh 9, tiền 11): có 3 người yếu hơn với số tiền $1, 2, 33$, nhưng chỉ được đấu 2 người ⇒ chọn 2 người giàu nhất ⇒ $11 + 33 + 2 =$ 46.
- Hiệp sĩ 4 (sức mạnh 7, tiền 33): 2 người yếu hơn có tiền $1, 2$ ⇒ $33 + 1 + 2 =$ 36.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Tham lam trực tiếp cho từng hiệp sĩ – O(N² log N)
Bài này dùng phương pháp tham lam. Số tiền của mọi người đều không âm, vậy cộng thêm càng nhiều thì càng giàu ⇒ mỗi hiệp sĩ nên cố đấu với càng nhiều người càng tốt. Nhưng khoan, chỉ "ăn" được tiền khi đấu với người yếu hơn thôi, chứ đấu với người mạnh hơn là mất sạch tiền luôn đấy haha.
Làm thẳng theo tư tưởng này: với mỗi hiệp sĩ $i$, duyệt hết $N$ hiệp sĩ để gom tiền của người yếu hơn, sắp xếp giảm dần rồi cộng $k$ số đầu. Mỗi hiệp sĩ tốn $O(N \log N)$, có $N$ hiệp sĩ ⇒ $O(N^2 \log N)$ – phức tạp quá với $N = 10^5$. Mình để code ở đây để các bạn hiểu ý tưởng và dùng làm code kiểm tra (vét cạn) thôi nhé.
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;
int main(){
int n, k;
cin >> n >> k;
vector<long long> p(n), c(n);
for(int i = 0; i < n; ++i){
cin >> p[i];
}
for(int i = 0; i < n; ++i){
cin >> c[i];
}
for(int i = 0; i < n; ++i){
vector<long long> t;
for(int j = 0; j < n; ++j){
if(p[j] < p[i]){
t.push_back(c[j]);
}
}
sort(t.begin(), t.end(), greater<long long>());
long long res = c[i];
for(int j = 0; j < k && j < (int)t.size(); ++j){
res += t[j];
}
cout << res << " ";
}
return 0;
}import sys
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
p = list(map(int, data[2:2 + n]))
c = list(map(int, data[2 + n:2 + 2 * n]))
out = []
for i in range(n):
t = [c[j] for j in range(n) if p[j] < p[i]]
t.sort(reverse=True)
out.append(c[i] + sum(t[:k]))
print(*out)Cách 2Sắp xếp + cửa sổ K số tiền lớn nhất – O(N log N)
Bước 1: Sắp xếp theo sức mạnh
Ta thấy chắc chắn phải cần đến sắp xếp để bài toán đơn giản hơn: sắp các hiệp sĩ tăng dần theo sức mạnh. Khi đó hiệp sĩ ở vị trí $i$ chỉ có thể thắng đúng $i$ hiệp sĩ đứng trước nó. Ví dụ 5 hiệp sĩ sau khi sắp có index $0..4$, hiệp sĩ ở index 3 thắng được các hiệp sĩ ở index $0, 1, 2$.
Bước 2: Cửa sổ chứa K số tiền lớn nhất (Sliding Window)
Duyệt từ index 0 (yếu nhất) trở đi. Ta cần biết tổng $k$ số tiền lớn nhất trong các hiệp sĩ đứng trước. Một cách tối ưu là dùng kỹ thuật cửa sổ trượt:
- Mảng $c$ chứa tối đa $k$ số tiền lớn nhất của các hiệp sĩ đứng trước $i$, biến
sumlà tổng các số trong $c$ (ban đầu 0). - Xét hiệp sĩ $i$: lưu số tiền ban đầu vào biến tạm
temp, rồi đáp án của hiệp sĩ này làtemp + sum. Phải dùngtempvì sau đó ta đưa số tiền gốc vào $c$, chứ đưa số tiền đã cộngsumvào là sai. - Nếu $c$ còn chưa đủ $k$ phần tử: thêm
tempvào $c$, cộng vàosum. Khi vừa đủ $k$ phần tử thì sắp xếp $c$ giảm dần (chỉ một lần duy nhất). - Nếu $c$ đã đủ $k$: nếu
temp$\le$ phần tử nhỏ nhất $c[k-1]$ thì bỏ qua; ngược lại loại $c[k-1]$ ra và chèntempvào, cập nhậtsum += temp - c[k-1].
temp vào đúng chỗ bằng sắp xếp chèn (Insertion Sort) chỉ tốn $O(K)$, thay vì gọi lại sort tốn $O(K \log K)$ cho mỗi lần. Còn sum chỉ cập nhật phần chênh lệch, không phải cộng lại cả $K$ phần tử.Cụ thể bước chèn: chắc chắn temp $\gt c[k-1]$ rồi nên xét $j$ từ $k-2$ ngược lên. Gặp $c[j] \lt$ temp thì đẩy $c[j]$ lùi xuống $c[j+1]$; gặp $c[j] \ge$ temp thì đặt temp vào $c[j+1]$ rồi break. Nếu temp lớn hơn tất cả thì vòng lặp chạy hết, $j = -1$, ta đặt temp vào $c[0]$.
Bước 3: In đúng thứ tự ban đầu bằng mảng đánh dấu
Sắp xếp xong thì thứ tự hiệp sĩ đã bị xáo trộn, mà đề yêu cầu in theo thứ tự input. Có bạn sẽ lưu mảng sức mạnh ban đầu rồi tìm kiếm nhị phân vị trí từng hiệp sĩ – được, nhưng tốn $O(N \log N)$.
Tối ưu hơn là thêm trường ID = index trong input vào struct (ID đi theo khi sắp xếp), và mảng res với res[ID] là đáp án của hiệp sĩ có ID đó. Tính xong hiệp sĩ $a[i]$ thì gán res[a[i].ID] = a[i].Money. Cuối cùng in res[0..n-1] là đúng thứ tự, chỉ $O(N)$.
Minh hoạ cửa sổ K số tiền lớn nhất
Em nhập dữ liệu rồi bấm Tiếp để xem các hiệp sĩ (đã sắp theo sức mạnh) lần lượt được xét và cửa sổ $c$ thay đổi ra sao:
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;
struct Data{
long long Money;
int Power, ID;
};
bool cmp(const Data &a, const Data &b){
return a.Power < b.Power;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
Data a[n];
for(int i = 0; i < n; ++i){
cin >> a[i].Power;
a[i].ID = i;
}
for(int i = 0; i < n; ++i){
cin >> a[i].Money;
}
sort(a, a + n, cmp);
int c[k + 1], idx = 0;
long long sum = 0, res[n];
for(int i = 0; i < n; ++i){
int temp = a[i].Money;
a[i].Money += sum;
res[a[i].ID] = a[i].Money;
if(idx < k){
c[idx++] = temp;
sum += temp;
if(idx == k){
sort(c, c + k, greater<int>());
}
}
else if(k > 0){
if(temp > c[k - 1]){
sum += temp - c[k - 1];
int j;
for(j = k - 2; j >= 0; --j){
if(temp > c[j]){
c[j + 1] = c[j];
}
else{
c[j + 1] = temp;
break;
}
}
if(j == -1){
c[0] = temp;
}
}
}
}
for(int i = 0; i < n; ++i){
cout << res[i] << " ";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
power = data[2:2 + n]
money = data[2 + n:2 + 2 * n]
a = sorted(range(n), key=lambda i: int(power[i])) # ID các hiệp sĩ, tăng dần theo sức mạnh
c = [] # tối đa k số tiền lớn nhất, giữ giảm dần
total = 0 # tổng các số trong c
res = [0] * n
for i in a:
temp = int(money[i])
res[i] = temp + total
if len(c) < k:
c.append(temp)
total += temp
if len(c) == k:
c.sort(reverse=True)
elif k > 0 and temp > c[k - 1]:
total += temp - c[k - 1]
j = k - 2
while j >= 0 and temp > c[j]:
c[j + 1] = c[j]
j -= 1
c[j + 1] = temp
print(*res)int c[k] và nhánh else đọc thẳng c[k - 1]. Khi $k = 0$ (đề cho phép) thì đó là mảng 0 phần tử và c[-1] truy cập ra ngoài mảng. Code gốc vẫn AC trên web (khi biên dịch với -O2 thì may mắn ra đúng), nhưng chạy với trình kiểm tra lỗi bộ nhớ thì báo lỗi ngay. Nên ở đây mình sửa nhẹ: khai báo c[k + 1] và đổi thành else if(k > 0) cho chắc ăn nha các bạn.Giải thích một số chỗ trong code:
- 3 dòng đầu hàm main: giúp nhập xuất C++ nhanh gần bằng C. Bài này phải nhập $2 \cdot 10^5$ số và xuất $10^5$ số; bỏ 3 dòng này nộp lại sẽ thấy chậm hơn gần 4 lần đó.
bool cmp(const Data &a, const Data &b)chỉ định sắp tăng dần theoPower, truyền làm tham số thứ 3 củasort. Tham số nên để tham chiếu&để không phải copy cả struct (tốn thời gian), cònconstđể lỡ vô tình sửa nó trong hàm thì trình biên dịch báo lỗi – kỹ năng lập trình thôi ^^sort(c, c + k, greater<int>())sắp mảng $c$ giảm dần; bỏ tham số thứ 3 thì là tăng dần. Mảng số nguyên thì tự biết so sánh nên không cần hàmcmp.- Hàm
sortcủa thư viện luôn đảm bảo $O(N \log N)$. Đừng tự code Selection/Interchange/Bubble Sort $O(N^2)$ với $N = 10^5$ là TLE ngay. Nhưng khi dữ liệu đã có thứ tự như mảng $c$ thì dùng Insertion Sort mới tối ưu – hiểu nguyên lý các thuật toán sắp xếp mới thấy đáng giá chỗ này hehe. - Vòng
for jchính là bước chèntempvào $c$ để $c$ vẫn giảm dần, như mình đã phân tích ở trên.
Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng struct $N$ phần tử là $O(S \cdot N)$ với $S$ là kích thước một struct, mảng
res$O(N)$, mảng $c$ $O(K)$ ⇒ tổng quát $O(\max(S \cdot N, K))$, tức là $O(N)$. - Thời gian: đọc dữ liệu $O(2N)$; sắp xếp mảng $a$ $O(N \log N)$; vòng xử lý chính $O(N)$ lần lặp, trong đó sắp $c$ một lần $O(K \log K)$ và mỗi lần chèn $O(K)$ ⇒ tệ nhất $O(N \cdot K)$; in kết quả $O(N)$. Tổng: $O(2N) + O(N \log N) + O(K \log K) + O(N \cdot K) + O(N)$. Với $K \le 10$ thì thành phần lớn nhất là $O(N \log N)$ đến từ việc sắp xếp các hiệp sĩ.
Nhẩm với $N = 10^5$, $K = 10$: $2 \cdot 10^5 + 17 \cdot 10^5 + 40 + 10 \cdot 10^5 + 10^5 \approx 3 \cdot 10^6$, ít hơn ngưỡng 1 giây từ 10 đến 20 lần nên yên tâm không TLE.
vector, map thay cho mảng thường nên chậm hơn (map luôn tốn chi phí cân bằng cây, vector là mảng động). Về thuật toán thì các chỗ dễ làm chậm là: gọi sort lại mảng $c$ mỗi lần, cộng lại cả $c$ thay vì cập nhật sum, hay tìm kiếm nhị phân thay cho mảng đánh dấu ID. Code trên của mình chạy 140 ms trên web; muốn xuống 125 ms hay 109 ms thì có một "giải pháp tà đạo" là thêm pragma như #pragma GCC optimize("Ofast") lên đầu chương trình 😆. Nhưng thật ra chênh nhau vài chục ms gần như là như nhau, còn phụ thuộc server lúc nộp nữa, chỉ khi cách biệt lớn kiểu 650 ms với 140 ms mới đáng nói.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét