驚了，我怎么這么菜啊。。

題目鏈接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=3203

(luogu)https://www.luogu.org/problemnew/show/P3299

題解: 先講正常做法。

設(shè)\(S_i\)為\(i\)的前綴和，則顯然第\(i\)次答案為\(\max^i_{j=1} \frac{S_i-S_{j-1}}{x_i+id-jd}\)

那么很顯然就是要求從一個點\((x_i+id,S_i)\)到\((jd,S_{j-1})\)的斜率最大值啊。。三分凸殼就行了啊。。想什么呢。。。

---

下面是我的垃圾做法，有興趣的可以感受一下（我相信沒人有興趣）

考慮斜率優(yōu)化(我就是陷入套路無法自拔的垃圾)，首先為了方便我們把輸入的\(x_i\)加上\(id\)并記作\(x_0\), 目前的總和記作\(S\), \(1\)到\((i-1)\)的和記作\(S_i\)(和上面定義不同)，考慮\(i\)不比\(j\)差(\(i<j\))的條件: \[\frac{S-S_i}{x_0-id}>\frac{S-S_j}{x_0-jd}\]展開后解得\[x_0\ge\frac{iS-jS-iS_j+jS_i}{S_j-S_i}d\]考慮三個點\(i<j<k\), \(i\)不比\(j\)劣的條件是\[x_0\ge\frac{iS-jS-iS_j+jS_i}{S_j-S_i}d\] \(k\)不比\(j\)劣的條件是\[x_0\le\frac{jS-kS-jS_k+kS_j}{S_k-S_j}d\]若后者大于等于前者則無論\(x_0\)為何值此兩個條件至少滿足一個，\(j\)無用。

然后嘗試化這個式子: \[\frac{jS-kS-jS_k+kS_j}{S_k-S_j}\ge \frac{iS-jS-iS_j+jS_i}{S_j-S_i}\] \[iS_jS_k-iS_j^2-jS_iS_k+jS_iS_j+jSS_k-jSS_j-iSS_k+iSS_j\le jS_kS_j-jS_iS_k-kS_j^2+kS_iS_j+kSS_j-kSS_i-jSS_j+jSS_i\] \[(i-j)S_jS_k+(k-i)S_j^2+(j-k)S_iS_j+(j-i)SS_k+(i-k)SS_j+(k-j)SS_i\le 0\] 嘗試因式分解 \[(S_j-S)(iS_k-jS_k+kS_j-iS_j+jS_i-kS_i)\le 0\] 因為\(S_j-S\)顯然小于\(0\), 所以\[iS_k-jS_k+kS_j-iS_j+jS_i-kS_i\ge 0\] 這個東西一看就是可以拆添項的: \[iS_k-jS_k+kS_j-jS_j-iS_j+jS_j+iS_k-jS_k\le 0\] \[(j-k)(S_i-S_j)-(i-j)(S_j-S_k)\le 0\] \[\frac{S_i-S_j}{i-j}\le \frac{S_j-S_k}{j-k}\]

這是\(j\)無用的條件，所以只需要維護斜率不增的上凸殼即可

……

我真的蠢到一定境界了

代碼

當然是我的垃圾做法的代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #define llong long long using namespace std;struct Point {double x,y;Point() {}Point(llong _x,llong _y) {x = _x,y = _y;} }; const int N = 1e5; Point ch[N+3]; double s[N+3]; double a[N+3]; double qr[N+3]; int n,tp; double d;void insertpoint(Point x) {while(tp>1 && (ch[tp].y-ch[tp-1].y)*(x.x-ch[tp].x)>=(x.y-ch[tp].y)*(ch[tp].x-ch[tp-1].x)) {tp--;}tp++; ch[tp] = x; // printf("CH: size=%d ",tp); // for(int i=1; i<=tp; i++) printf("(%lf %lf) ",ch[i].x,ch[i].y); puts(""); }double query(double x,double sum) { // printf("query(%lf %lf)\n",x,sum);int left = 1,right = tp;while(left<right){int mid = (left+right+1)>>1;bool ok = x*(ch[mid].y-ch[mid-1].y)<=(ch[mid-1].x*ch[mid].y-ch[mid].x*ch[mid-1].y+ch[mid].x*sum-ch[mid-1].x*sum)*d ? true : false;if(ok) {left = mid;}else {right = mid-1;}} // printf("left=%d\n",left);double ret = (sum-ch[left].y)/(x-ch[left].x*d);return ret; }int main() {scanf("%d%lf",&n,&d);for(int i=1; i<=n; i++){scanf("%lf%lf",&a[i],&qr[i]);s[i] = s[i-1]+a[i-1];qr[i] += i*d;}s[n+1] = s[n]+a[n];double sans = 0.0;for(int i=1; i<=n; i++){insertpoint(Point(i,s[i]));double ans = query(qr[i],s[i+1]);sans += ans; // printf("i%d ans%lf\n",i,ans);}printf("%lld\n",(llong)(sans+0.5));return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3203 Luogu P3299 [SDOI2013]保护出题人 (凸包、斜率优化、二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。