- #pragmacomment(linker, "/STACK:1024000000,1024000000")
- #include
- #include
- #include
- #include
- #include
- #include
- #include<set>
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- const doublepi=acos(-1.0),eps=1e-10;
- void File()
- {
- freopen("D:\\in.txt","r",stdin);
- freopen("D:\\out.txt","w",stdout);
- }
- template <classT>
- inline voidread(T &x)
- {
- charc = getchar();
- x =0;
- while(!isdigit(c)) c = getchar();
- while(isdigit(c))
- {
- x = x *10+ c -'0';
- c = getchar();
- }
- }
- int n,t;
- long longx[500000],dp[500000],s[500000];
- intq[500000],f1,f2;
- booldelete1(inta,intb,int c)
- {
- if(dp[b]-s[b]-x[b+1]*(c-b)<=dp[a]-s[a]-x[a+1]*(c-a))return 1;
- return 0;
- }
- booldelete2(inta,intb,int c)
- {
- if(
- ((dp[c]-s[c]+x[c+1]*c)-(dp[b]-s[b]+x[b+1]*b))*(x[b+1]-x[a+1]) <=
- ((dp[b]-s[b]+x[b+1]*b)-(dp[a]-s[a]+x[a+1]*a))*(x[c+1]-x[b+1])
- ) return 1;
- return 0;
- }
- int main()
- {
- while(~scanf("%d%d",&n,&t))
- {
- for(inti=1;i<=n;i++) scanf("%lld",&x[i]);
- sort(x+1,x+1+n);
- for(inti=1;i<=n;i++) s[i]=s[i-1]+x[i];
- for(inti=t;i<2*t;i++) dp[i]=s[i]-x[1]*i;
- f1=f2=0; q[0]=0; f2++; q[f2]=t;
- for(inti=2*t;i<=n;i++)
- {
- while(1)
- {
- if(f2-f1+1<2)break;
- if(delete1(q[f1],q[f1+1],i)) f1++;
- else break;
- }
- dp[i]=dp[q[f1]]+s[i]-s[q[f1]]-x[q[f1]+1]*(i-q[f1]);
- while(1)
- {
- if(f2-f1+1<2)break;
- if(delete2(q[f2-1],q[f2],i-t+1)) f2--;
- else break;
- }
- f2++; q[f2]=i-t+1;
- }
- printf("%lld\n",dp[n]);
- }
- return 0;
- }
来源: