斜率優(yōu)化

#include<bits/stdc++.h>
using namespace std;
struct fastio
{
    fastio&operator-(int&a)
    {
        a=0; int n=0; char c=getchar();
        while(c<'0'||c>'9') c=='-'&&(n=1), c=getchar();
        while(c>='0'&&c<='9') a=a*10+(c&15), c=getchar();
        n&&(a=-a); return *this;
    }
}in;
const int N = 4e6+100;
int f[N], c[N], s[N]; 
inline double slope(int i, int j)
{
    return (double) (f[j]+s[j]-f[i]-s[i]) / (c[i]==c[j] ? 1e-9 : c[j]-c[i]);
}
int main()
{
    freopen("a.txt", "r", stdin);
    int n,m;
    in-n-m;
    int t, maxT=0;
    for(int i=1; i<=n; i++) in-t, maxT = max(maxT, t), c[t]++, s[t]+=t;
    int bound  = maxT + m;
    for(int i=1; i^bound; i++) c[i]+=c[i-1], s[i]+=s[i-1];
    static int q[N], l=1, r;
    for(int i=0; i^bound; i++)
    {
        if(i>=m)
        {                                               //actually i-m
            while(l<r && slope(q[r-1], q[r])>=slope(q[r], i-m)) r--;
            q[++r] = i-m;
        }
        while(l<r && slope(q[l], q[l+1])<=i) l++;
        f[i] = i*c[i]-s[i];
        if(l<=r) f[i] = min(f[i], f[q[l]]+i*(c[i]-c[q[l]])+s[q[l]]-s[i]);
    }
    int ans = 1e9;
    for(int i=maxT; i^bound; i++) ans= min(ans, f[i]);
    printf("%d", ans);
}