Tổng Lớn Nhất Đạt Được Từ Một Hoán Vị Bất Kỳ
Đề bài
Cho một mảng số nguyên nums và một mảng các yêu cầu requests với requests[i] = [start_i, end_i]. Yêu cầu thứ $i$ yêu cầu tính tổng:
Cả start_i và end_i đều được đánh chỉ số từ 0.
Hãy tìm tổng lớn nhất của tất cả các yêu cầu khi xét trên mọi hoán vị có thể có của mảng nums. Vì đáp án có thể rất lớn, hãy trả về kết quả modulo $10^9 + 7$.
Input
- Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$) là kích thước của mảng
nums. - Dòng thứ hai chứa $n$ số nguyên
nums[0], nums[1], …, nums[n-1]($0 \le$ nums[i] $\le 10^5$) là các phần tử của mảng. - Dòng thứ ba chứa một số nguyên $q$ ($1 \le q \le 10^5$) là số lượng yêu cầu.
- $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên
start_ivàend_i($0 \le$ start_i $\le$ end_i $\lt n$) mô tả một yêu cầu.
Output: một số nguyên duy nhất là tổng lớn nhất tìm được sau khi lấy modulo $10^9 + 7$.
Subtask
- 20% số test đầu tiên có $n, q \le 9$.
- 50% số test tiếp theo có $n, q \le 10^4$.
- 30% số test còn lại không có giới hạn gì thêm.
| Input | Output | Giải thích |
|---|---|---|
5 1 2 3 4 5 2 1 3 0 1 | 19 | Một hoán vị của nums là [2,1,3,4,5] cho tổng: yêu cầu [1,3] → 1 + 3 + 4 = 8; yêu cầu [0,1] → 2 + 1 = 3; tổng = 11. Một hoán vị tối ưu là [3,5,4,2,1] cho tổng: yêu cầu [1,3] → 5 + 4 + 2 = 11; yêu cầu [0,1] → 3 + 5 = 8; tổng = 19. |
6 1 2 3 4 5 6 1 0 1 | 11 | Hoán vị tối ưu là [6,5,4,3,2,1]. Tổng yêu cầu [0,1] = 6 + 5 = 11. |
6 1 2 3 4 5 10 3 0 2 1 3 1 1 | 47 |
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 và kèm lời giải để 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 😇.
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 OJBạ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 CodeforcesTóm tắt đề bài: cho một dãy số $a$ gồm $N$ số nguyên và một mảng request, mỗi request gồm 2 số start và end, ta cần tính tổng a[start] + a[start + 1] + … + a[end], rồi cộng trên toàn bộ request. Xét toàn bộ các hoán vị của mảng $a$, chọn ra hoán vị sao cho tổng này lớn nhất, in phần dư khi chia cho $10^9 + 7$.
100%Ý tưởng: tần suất xuất hiện + sắp xếp
Vì ta tính tổng các giá trị sau toàn bộ truy vấn, nên nếu gọi freq[i] là số lần vị trí $i$ được tính sau toàn bộ các request, thì kết quả chính là tổng các a[i] * freq[i]. Việc đầu tiên là phải build ra được mảng freq.
freq[start] lên 1 đơn vị, giảm freq[end + 1] xuống 1 đơn vị. Sau đó duyệt $i$ từ 1 đến $n - 1$: freq[i] += freq[i - 1]. Như vậy mỗi request chỉ tốn $O(1)$ thay vì phải cộng 1 cho từng vị trí trong đoạn.Ví dụ 1 với 2 request [1, 3] và [0, 1]:
| Vị trí | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| freq sau khi +1 / −1 | +1 | +1 | -1 | 0 | -1 |
| freq sau khi cộng dồn | 1 | 2 | 1 | 1 | 0 |
Khi đã có bảng freq rồi, ta cần chọn ra một hoán vị của dãy $a$ sao cho tổng a[i] * freq[i] lớn nhất. Để tổng này lớn nhất thì số lớn nhất cần đặt ở vị trí có tần suất nhiều nhất, số lớn nhì đặt ở vị trí có tần suất lớn nhì, … Do đó ta sắp xếp mảng freq tăng dần, sắp xếp mảng $a$ tăng dần, rồi lấy tổng các a[i] * freq[i] với mọi $i$:
| freq (tăng dần) | 0 | 1 | 1 | 1 | 2 |
|---|---|---|---|---|---|
| nums (tăng dần) | 1 | 2 | 3 | 4 | 5 |
| Tích | 0 | 2 | 3 | 4 | 10 |
| Tổng | 0 + 2 + 3 + 4 + 10 = 19 | ||||
Vì sao ghép lớn với lớn là tốt nhất? (mình giải thích thêm)
Giả sử có 2 vị trí với tần suất $f_1 \le f_2$ và 2 số $x \le y$. Đặt $y$ vào vị trí $f_2$ cho tổng $x f_1 + y f_2$, còn đặt ngược lại cho $y f_1 + x f_2$. Hiệu giữa hai cách là $(y - x)(f_2 - f_1) \ge 0$, nên đặt số lớn vào vị trí tần suất lớn không bao giờ tệ hơn. Cứ đổi chỗ từng cặp "ngược" như vậy thì sẽ ra cách ghép đã sắp xếp cùng chiều (đây chính là bất đẳng thức hoán vị).
Em nhập mảng nums và các request (mỗi request 2 số start end) rồi bấm Tiếp để xem từng bước: đánh dấu mảng hiệu, cộng dồn ra tần suất, rồi sắp xếp ghép lớn với lớn:
Đánh giá độ phức tạp: $O(N \log N)$ cho 2 lần sắp xếp, cộng $O(q)$ cho việc xử lý request.
Source code đã nộp thành công:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long freq[100005];
int maxSumRangeQuery(vector<int> &nums, vector<vector<int>> &requests){
int n = (int)nums.size();
// Reset mảng freq
memset(freq, 0, sizeof(freq));
// Áp dụng kỹ thuật mảng hiệu (difference array)
for(int i = 0; i < (int)requests.size(); i++){
freq[requests[i][0]]++;
freq[requests[i][1] + 1]--;
}
// Tính tần suất thực tế bằng tổng tích lũy
for(int i = 1; i < n; i++){
freq[i] += freq[i - 1];
}
// Sắp xếp tần suất và mảng nums
sort(freq, freq + n);
sort(nums.begin(), nums.end());
// Tính tổng: ghép số lớn nhất với tần suất lớn nhất
long long ans = 0LL;
for(int i = 0; i < n; i++){
ans = (ans + (1LL * nums[i] * freq[i]) % MOD) % MOD;
}
return (int)ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
// Đọc mảng nums
cin >> n;
vector<int> nums(n);
for(int i = 0; i < n; i++){
cin >> nums[i];
}
// Đọc số lượng requests
cin >> q;
vector<vector<int>> requests(q, vector<int>(2));
for(int i = 0; i < q; i++){
cin >> requests[i][0] >> requests[i][1];
}
// Tính kết quả
int result = maxSumRangeQuery(nums, requests);
// In kết quả
cout << result << endl;
return 0;
}import sys
MOD = 1000000007
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
nums = list(map(int, data[1:1 + n]))
q = int(data[1 + n])
freq = [0] * (n + 1)
# Kỹ thuật mảng hiệu (difference array)
pos = 2 + n
for _ in range(q):
start = int(data[pos]); end = int(data[pos + 1]); pos += 2
freq[start] += 1
freq[end + 1] -= 1
# Tính tần suất thực tế bằng tổng tích lũy
for i in range(1, n):
freq[i] += freq[i - 1]
# Sắp xếp tần suất và mảng nums, ghép số lớn nhất với tần suất lớn nhất
freq = sorted(freq[:n])
nums.sort()
ans = 0
for i in range(n):
ans = (ans + nums[i] * freq[i]) % MOD
print(ans)
main()long long và lấy modulo trong lúc cộng như code ở trên. Lấy modulo sau khi đã chọn được hoán vị tốt nhất là đúng, vì việc so sánh "tổng nào lớn hơn" được làm trên giá trị thật (thông qua sắp xếp), không phải trên giá trị đã modulo.Mình đã kiểm tra code với 150 bộ test ngẫu nhiên so với cách thử mọi hoán vị, đều cho cùng kết quả. Với $n = q = 10^5$, bản C++ chạy khoảng 0.04 giây, bản Python mình viết thêm khoảng 0.12 giây.
Nhận xét
Đăng nhận xét