- /*
- 1. 考虑对所有同学的时间进行排序, 问题转化为:
- 如何将数轴分为长度不小于 m 的几段, 使每段中的点到右端点的距离之和最短
- 2. 设 f[i]表示从 (0,i] 区间内, 并以 i 为右端点结束的最小时间
- 那么考虑转移:
- f[i]=min(f[j]+∑i-t[k])
- (i-2*m<=j<=i-m+1)
- (为什么是 i-2*m 的下界? 因为如果大于 i-2*m, 完全可以再分一段, 得到不劣
- 的答案!)
- 考虑整理一下:
- f[i]=min(f[j]+(num[i]-num[j])*i-(sum[i]-sum[j]))
- sum[i]表示以 i 为右端点的所有时间之和
- num[i]表示 [0,i] 范围内的所有点的数目
- 同时可以考虑剪枝:
- if(num[i]==num[j])
- f[i]=f[j];
- */
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- const int N=4000002;
- int num[N],sum[N],n,m,t[N],f[N],tmp,ans=2147483647;
- inline int max(int x,int y)
- {
- return x>y?x:y;
- }
- inline int min(int x,int y)
- {
- return x<y?x:y;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&t[i]);
- num[t[i]]++;
- sum[t[i]]+=t[i];
- tmp=max(tmp,t[i]);
- }
- for(int i=1;i<=tmp+m;i++)
- sum[i]+=sum[i-1],num[i]+=num[i-1];
- for(int i=1;i<=tmp+m;i++)
- {
- f[i]=num[i]*i-sum[i];
- if(i>=m&&num[i]==num[i-m])
- {
- f[i]=f[i-m];
- continue;
- }
- for(int j=max(i-m-m+1,0);j<=i-m;j++)
- f[i]=min(f[j]+i*(num[i]-num[j])-(sum[i]-sum[j]),f[i]);
- }
- for(int i=tmp;i<tmp+m;i++)
- ans=min(ans,f[i]);
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3266937.html