前言

作为NOIP-J的T3，这道题在一定程度上是会有区分度的。。。
比如说这道题就有一堆解法：

• 剪枝优化状态
• 斜率优化DP
• 的神级DP
• 某位大佬说的算法
  但我这里就主要讲一下斜率优化DP吧，相信大部分都是这种做法吧

分析

我们考虑枚举
设
DP[i]表示在时回到人大附中的最少总时间
Pre[i]表示及之前的时间前缀
Cnt[i]表示及之前的人数前缀
所以我们可以列出一个朴素的DP方程：

看到这个类似于直线方程的转移方式，我们开始考虑斜率优化
设
当优于时

所以，我们就得到了斜率优化的比较方式。
这道题也就Okay了！

代码

//P5017
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MAXN=5e6+10;

int Queue[MAXN],Head=1,Tail;
int Total,Time,Num[MAXN],Max;
int Pre[MAXN],Cnt[MAXN];
double DP[MAXN],Ans=1e18;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline double Slope(int X,int Y) { return (double)(Pre[Y]-Pre[X]+DP[Y]-DP[X])/(Cnt[Y]==Cnt[X] ? 1e-9 : (double)(Cnt[Y]-Cnt[X])); }
int main() {
    //File();
    scanf("%d %d",&Total,&Time);
    FOR(i,1,Total) { scanf("%d",&Num[i]); Cnt[Num[i]]++; Pre[Num[i]]+=Num[i]; Max=max(Max,Num[i]); }
    FOR(i,1,Max+Time-1) { Cnt[i]+=Cnt[i-1]; Pre[i]+=Pre[i-1]; }
    FOR(i,0,Max+Time-1) {
        if(i-Time>=0) {
            while(Head<Tail && Slope(Queue[Tail-1],Queue[Tail])>=Slope(Queue[Tail],i-Time)) Tail--;
            Queue[++Tail]=i-Time;
        }
        while(Head<Tail && Slope(Queue[Head],Queue[Head+1])<=i) Head++;
        DP[i]=i*Cnt[i]-Pre[i];
        if(Head<=Tail) DP[i]=min(DP[i],DP[Queue[Head]]+(Cnt[i]-Cnt[Queue[Head]])*i-(Pre[i]-Pre[Queue[Head]]));
    }
    FOR(i,Max,Max+Time-1) Ans=min(Ans,DP[i]);
    printf("%.0f\n",Ans); 
    //fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}