本文最后更新于 714 天前,其中的信息可能已经有所发展或是发生改变。
Origional Link
思想:
- 贪心。
- 设仓库选址最佳处为 P,此时在该位置左侧存在 m 个货仓,右侧存在 n 个货仓,总距离为 L。
- 若更改货仓位置为 P−1,则总长度变为 L−m+n。
- 若更改货仓位置为 P+1,则总长度变为 L+m−n。
- 易知位置 P 处有: L−m+n=L+m−n 必然成立,可推出 m=n。
- 综上,最佳位置 P 应使得左右位置的货仓数量相等。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 1e6 + 3; |
| |
| int a[N]; |
| |
| typedef long long LL; |
| |
| void solve(){ |
| int n; cin >> n; |
| for(int i = 0; i < n; i ++) cin >> a[i]; |
| sort(a, a + n); |
| LL sum = 0; |
| for(int i = 0; i < n; i ++) sum += abs(a[n >> 1] - a[i]); |
| cout << sum << endl; |
| } |
| int main(){ |
| solve(); |
| return 0; |
| } |