Hướng dẫn cho Summer Contest #02 - Thống trị hòn đảo
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors: ,
Ý tưởng
Giả sử trung tâm được xây tại đảo \(x\).
Khi đó các đảo nằm trong phạm vi phục vụ là:
(sau khi cắt lại để nằm trong đoạn từ \(1\) đến \(N\)).
Tất cả người dân trên các đảo thuộc đoạn này sẽ không phải di chuyển quá xa.
Ngược lại, số người phải di chuyển quá xa bằng:
Do tổng dân toàn quần đảo là hằng số, để số người phải di chuyển quá xa là nhỏ nhất thì ta chỉ cần:
Tìm vị trí đặt trung tâm sao cho tổng dân trong đoạn phục vụ lớn nhất.
Gọi:
là tổng dân toàn quần đảo.
Với mỗi vị trí \(x\), ta cần tính:
trong đó:
Nếu biết nhanh tổng dân trên mọi đoạn liên tiếp thì ta sẽ tìm được giá trị lớn nhất.
Xây dựng mảng cộng dồn:
Khi đó tổng dân trên đoạn \([l,r]\) được tính trong:
bằng công thức:
Duyệt mọi vị trí đặt trung tâm \(x\) từ \(1\) đến \(N\):
- Tính đoạn phục vụ \([l,r]\).
- Tính tổng dân được phục vụ.
- Cập nhật giá trị lớn nhất.
Sau cùng:
Code AC (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("thongtrihondao.inp","r",stdin);
freopen("thongtrihondao.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<long long> d(n + 1, 0);
vector<long long> prefix_sum(n + 1, 0);
long long total_population = 0;
for (int i = 1; i <= n; ++i) {
cin >> d[i];
total_population += d[i];
prefix_sum[i] = prefix_sum[i - 1] + d[i];
}
long long max_served = 0;
for (int x = 1; x <= n; ++x) {
int L = max(1, x - k);
int R = min(n, x + k);
long long current_served = prefix_sum[R] - prefix_sum[L - 1];
if (current_served > max_served) {
max_served = current_served;
}
}
cout << total_population - max_served << "\n";
return 0;
}
Bình luận