斜率優(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);
}
