@[haber](/user/345900) 前后缀没区别的
by fanypcd @ 2022-07-20 22:15:36
一年后本蒟蒻也推出了同样的式子，同样喜提 $58pts$ （~~最后写李超树才过掉~~），个人认为是因为会出现这种情况：
$\frac{weight_k\times dis_k-weight_j\times dis_j}{weight_k-weight_j}$ 这个值并不与 $k$ 和 $j$ 的取值存在单调性，因此可能导致当前队首的两个值满足这个关系，第三个数加入队列时也与第二个数满足这个关系，被加入队列。但是后面随着 $i$ 的增大 $dis_i$ 也增大，可能当前队首的两个值仍然满足这个关系，但是由于不存在单调性，就会导致第三个数可能与第二个数不满足这种关系，第三个数也可能与第一个数也不满足这种关系，导致选择错误。
您可以用您的代码看一下本蒟蒻的这组数据跑到第六个位置时队列第二个数与队列头，第三个数与第二个数，第三个数与队列头时是否满足这种关系。
$input:$
```
6
5 7
1 2
6 5
10 1
6 4
10 8
```
$AC$ $output:$
```
121
```
@[Haber](/user/345900)
by prokali @ 2023-09-08 19:38:22
@[prokali](/user/577796) 然后因为题解中的后缀柿子虽然也是 $>dis_i$ ，但是后缀 $dis_i$ 是单减而不是单增的，所以不存在这种问题
by prokali @ 2023-09-08 19:44:29
@[prokali](/user/577796) 啊我真没想过这个问题。谢谢指点！
by Haber @ 2023-09-08 20:54:06
@[Haber](/user/345900) 额，我今天又改了一下自己的代码，发现前缀是可以的，您的代码我也看了一下，事实上是因为这一句：
```
while(head<tail&&(sq(i)-sq(q[tail]))*(weight[q[tail]]-weight[q[tail-1]])<(sq(q[tail])-sq(q[tail-1])*(weight[i]-weight[q[tail]]))) tail--;
```
中
```
(sq(q[tail])-sq(q[tail-1])*(weight[i]-weight[q[tail]]))
```
括号位置写错了导致队尾判断出了问题，应该改为
```
(sq(q[tail])-sq(q[tail-1]))*(weight[i]-weight[q[tail]])
```
再因为乘法可能爆 $int$ 开一个 $long $ $long$ 就可以了，非常抱歉于昨日蒟蒻错误的分析！
修改后您的代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans=2e9;
const int N=2e4+4;
int f[N];
int tot;
int dis[N],weight[N];
int head=1,tail=1;
int q[N],d[N],w[N];
int sq(int i){
return weight[i]*dis[i];
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>d[i];
dis[i+1]=dis[i]+d[i]; //Before i this point.
weight[i]=weight[i-1]+w[i];
}
for(int i=1;i<=n+1;i++) tot+=(dis[n+1]-dis[i])*w[i];
for(int i=1;i<=n;i++){
while(head<tail&&sq(q[head+1])-sq(q[head])<dis[i]*(weight[q[head+1]]-weight[q[head]])) head++;
f[i]=tot-weight[q[head]]*(dis[n+1]-dis[q[head]])-(weight[i]-weight[q[head]])*(dis[n+1]-dis[i]);
while(head<tail&&(sq(i)-sq(q[tail]))*(weight[q[tail]]-weight[q[tail-1]])<(sq(q[tail])-sq(q[tail-1]))*(weight[i]-weight[q[tail]])) tail--;
q[++tail]=i;
}
for(int i=1;i<=n;i++) ans=min(ans,f[i]);
cout<<ans<<endl;
return 0;
}
```
by prokali @ 2023-09-09 16:21:28
@[prokali](/user/577796) 感谢大佬，关注了，我是瞎子
by Haber @ 2023-09-09 16:26:31
@[Haber](/user/345900) 昨天我个人说的问题是不存在的，因为
```
可能当前队首的两个值仍然满足这个关系，但是由于不存在单调性，就会导致第三个数可能与第二个数不满足这种关系，第三个数也可能与第一个数也不满足这种关系
```
这句话中如果第一个数与第二个数算出来的值比加入的第三个数与第二个数算出来的值大，那么在正确的抛尾代码中第二个数就会被扔掉，所以不会存在这种情况，再次为对您的打扰抱歉！
by NATO @ 2023-09-09 16:28:03