一道很好的構造題
原題鏈接
很快就能想到，撿每個垃圾的能量可以最后再算。然后，對于每個垃圾，在路上耗費的能量僅與它是第幾個被撿的有關，于是我們考慮將垃圾分組。
首先，我們定義\(F(x,i)\)為某次從\(0\)出發，撿到坐標為\(x\)的垃圾的次序為\(i\)的花費，則有：

\(F(x,i)=\left\{\begin{matrix} 5x\ \ (i=1)\\ (2i-1)x\ \ (i>1) \end{matrix}\right.\)
由上式，易知對于每一組，讓機器人先撿最右邊的垃圾，然后往回一個一個撿是最優的。同時，將所有垃圾從后往前按一個固定的間隔\(k\)分組是最優的。
所以，我們只需要枚舉\(k\)，再利用前綴和，\(O(logn)\)計算組間距為\(k\)的花費，更新一下答案就行了。
為什么是\(O(logn)\)？因為調和級數的性質，\(\sum\limits_{i=1}^n\frac{1}{i}=logn+O(1)\)。
因為中途計算時可能會爆\(long long\)，所以我們要特判一下，當前的花費大于等于\(ans\)時就可以跳出循環了。
Code： #include <bits/stdc++.h>using namespace std;#define ll long longint n; ll x, ans = (ll)9e18, a[200005];int main() {cin >> n >> x;for(int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i-1];for(int k = 1; k <= n; ++k) {ll coef = 3LL, sum = 0;for(int i = n; i >= 1; i -= k) {sum += (a[i]-a[max(0, i-k)])*max(coef, 5LL), coef += 2;if(sum >= ans) break; //防爆long long}ans = min(ans, sum+(k+n)*x);}cout << ans << endl;return 0; }

轉載于:https://www.cnblogs.com/dummyummy/p/9660416.html

總結

以上是生活随笔為你收集整理的AGC027B Garbage Collector的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。