for(int i=1;i<=n;i++){ while(l<r&&(t[i]+s)*(c[q[l]]-c[q[l+1]])<=f[q[l]]-f[q[l+1]]) l++; f[i]=f[q[l]]+t[i]*(c[i]-c[q[l]])+s*(c[n]-c[q[l]]); while(l<r&&(c[i]-c[q[r]])*(f[q[r]]-f[q[r-1]])>=(c[q[r]]-c[q[r-1]])*(f[i]-f[q[r]])) r--; //这里这个while循环为什么是这样子? //这里是交叉相乘,f的那一项是Y,因此左边代表r-1与r的斜率,右边代表i与r的斜率。 //那么,此题维护的是单调递增的斜率,那么应该保证尾部斜率大于当前斜率(i点与q[tt]点斜率),也就是尾部斜率小于等于当前斜率时弹出队尾 //但是代码中是 尾部斜率(左)大于当前斜率(右) 啊 q[++r]=i; }