题目大意：
在一条直线上，有n个老鼠，m个洞。
每个老鼠i都有一个初始位置x[i]。
每个洞i都有一个固定位置p[i]和容量限制c[i]。
求所有老鼠都进洞的最小距离总和。
思路：
动态规划。
用f[i][j]表示前i个洞、前j只老鼠的最小距离总和。
用sum[i][j]表示前j个老鼠都进入第i个洞的距离总和。
可以得到以下DP方程：
f[i][j]=min{f[i-1][k]-sum[i][k]|k<=j}+sum[i][j]。
然后就MLE，发现sum可以每次求出来，f如果倒着推，也可以省掉一维。
这样空间复杂度就是O(n)的，时间复杂度是O(n^2m)的，在第42个点TLE了。
考虑使用单调队列维护f[i-1][k]-sum[i][k]的min，做到O(nm)。
#include<deque>
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) if(ch=='-') neg=true;
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return neg?-x:x;
}
const long long inf=0x7fffffffffffffffll;
const int N=;
int x[N];
struct Hole {
int p,c;
bool operator < (const Hole &another) const {
return p<another.p;
}
};
Hole h[N];
long long f[][N],sum[N];
std::deque<int> q;
int main() {
int n=getint(),m=getint();
for(register int i=;i<=n;i++) {
x[i]=getint();
}
for(register int i=;i<=m;i++) {
h[i]=(Hole){getint(),getint()};
}
std::sort(&x[],&x[n+]);
std::sort(&h[],&h[m+]);
std::fill(&f[][],&f[][n+],inf);
for(register int i=;i<=m;i++) {
for(register int j=;j<=n;j++) {
sum[j]=sum[j-]+std::abs(h[i].p-x[j]);
}
q.clear();
q.push_back();
for(register int j=;j<=n;j++) {
while(!q.empty()&&j-q.front()>h[i].c) {
q.pop_front();
}
while(!q.empty()&&f[!(i&)][j]-sum[j]<=f[!(i&)][q.back()]-sum[q.back()]) {
q.pop_back();
}
q.push_back(j);
f[i&][j]=f[!(i&)][q.front()]+sum[j]-sum[q.front()];
}
}
printf("%I64d\n",f[m&][n]!=inf?f[m&][n]:-);
return ;
}