深刻意识到自己从来没弄懂过wqs二分。

while(l<=r){//WA
    int mid=l+r>>1;
    calc(mid);
    if(g[n]>k)l=mid+1;
    else ans=f[n]-g[n]*mid,r=mid-1;
}

while(l<=r){//AC
    int mid=l+r>>1;
    calc(mid);
    if(g[n]>k)l=mid+1;
    else ans=f[n]-k*mid,r=mid-1;
}

对于凸包上三点共线的情况，我们只会保留最左/最右的点，截距相同，但真正的y值要加上k倍的斜率。

希望没人和我一样因为这个调2h qwq