2023-07-26 16:14:50
思考
考虑如何暴力转移，观察到老鼠之间的路线如果交叉或者包含都不是最优的，所以我们可以设计状态 \(f[i][j]\) 表示把前 \(j\) 只老鼠全部放在前 \(i\) 的洞里的最小步数。然后转移就是:
\(f[i][j]=min\{f[i-1][k]+sum[j]-sum[k]\}\)，\(sum[j]\) 表示把 \(j\) 只老鼠都放进 \(i\) 的最小距离，可以用差分 \(sum[j]-sum[k]\) 算出把 \([k+1,j]\) 都放进 \(i\) 的最小距离。
\(min\{f[i-1][k]+sum[j]-sum[k]\}\) 显然可以用单调队列优化，当 \(j-k>size[i]\) 时就弹出即可。
\(Code\)
typedef long long ll;
typedef pair<int,int> PII;
int n,m,a[5005],s[5005];
ll f[2][5005],sum[5005];
PII b[5005];
queue<int>Q;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=m;i++){
b[i].first=read(),b[i].second=read();
}
sort(a+1,a+1+n),sort(b+1,b+1+m);
for(int i=1;i<=m;i++)s[i]=s[i-1]+b[i].second;
if(s[m]<n)return puts("-1"),0;
int o=0;
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=m;i++){
o^=1;
f[o][0]=0,Q.push(0);
for(int j=1;j<=s[i]&&j<=n;j++){
f[o][j]=f[o^1][j],sum[j]=sum[j-1]+abs(a[j]-b[i].first);
while(!Q.empty()&&((j-Q.front()>b[i].second)||f[o^1][Q.front()]-sum[Q.front()]>f[o^1][j]-sum[j]))Q.pop();
Q.push(j);
f[o][j]=min(f[o][j],f[o^1][Q.front()]+sum[j]-sum[Q.front()]);
}
while(!Q.empty())Q.pop();
}
printf("%lld",f[o][n]);
}