## Bài toán yêu cầu bạn chọn một ngôi nhà $x$ và tính chi phí nhỏ nhất để thăm tất cả nhà còn lại khi xuất phát từ nhà ấy.
## Một hướng giải là biến đổi phương diện đường tròn của dãy nhà và lập mảng tiền tố tương ứng để duyệt khoảng cách nhỏ nhất cho mỗi nhà từ $i$. Có thể giải như sau:
- Dễ dàng thấy -- Những ngôi nhà gần nhất với nhà thứ $i$ sẽ có khoảng cách không vượt quá $\left\lfloor \frac{n}{2} \right\rfloor$, nên bạn chỉ cần duyệt các nhà nằm trên hai nửa đường tròn từ gốc $i$.
- Để thuận tiện tính toán, bạn sẽ mô phỏng vị trí thăm của dãy nhà theo tính đi vòng của đường tròn bằng cách ánh xạ mỗi chỉ số phần tử trong mảng $A$ thêm $n$ vị trí, tức:
\begin{equation}
A[i + n] = A[i]
\end{equation}
- Với mảng mở rộng này, bạn sẽ lập hai mảng tổng tiền tố, ví dụ gọi là $pre$ và $prex$ như sau:
\begin{equation}
pre[i] = pre[i - 1] + A[i]
\end{equation}
\begin{equation}
prex[i] = prex[i - 1] + i \cdot A[i]
\end{equation}
- Qua ánh xạ, bạn sẽ thấy mảng A phân bố như đường tròn, vòng về nhà $1$ từ nhà $n$ tại chỉ số $n + 1$:
\begin{equation}
1 \quad 2 \quad 3 \quad .. \quad i \quad .. \quad n - 1 \quad n \quad 1 \quad 2 \quad 3 \quad .. \quad i \quad .. \quad n - 1 \quad n
\end{equation}
- Dãy nằm giữa hai vị trí đối xứng trên mảng ($A[i]$ và $A[i + n]$) sẽ bao chứa tất cả các nhà ngoài nhà $i$, nên bạn sẽ tính được chi phí nhỏ nhất bằng hai mảng tiền tố đã lập.
### Code tham khảo:
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LIM = 1e5 + 5;
const int INF = LLONG_MAX;
int n, k;
int shelf[2 * LIM], pre[2 * LIM], prex[2 * LIM];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> shelf[i];
shelf[i + n] = shelf[i];
}
for (int i = 1; i <= 2 * n; ++i) {
pre[i] = pre[i - 1] + shelf[i];
prex[i] = prex[i - 1] + i * shelf[i];
}
int ans = INF;
for (int i = 1; i <= n; ++i) {
int k = n / 2;
int cw1 = prex[i + k] - prex[i];
int cw2 = i * (pre[i + k] - pre[i]);
int ccw1 = (i + n) * (pre[i + n - 1] - pre[i + k]);
int ccw2 = prex[i + n - 1] - prex[i + k];
ans = min(ans, cw1 - cw2 + ccw1 - ccw2);
}
cout << ans;
}
```
noice
Created at
1 likes