http://poj.org/problem?id=3709 (题目链接)
题意
给出一个n个数的序列，要求将其中一些数改为另一个比它小的数，改动的花费为两数的绝对值，完成改动后使得整个序列中出现过的数出现的次数大于等于K。求最小花费。
Solution
将原序列从大到小排序以后，我们可以发现，每次把连续的一段改成相同的数总是比离散的修改更优。于是我们写出dp方程：${f[i]=Min(f[j]+s[i]-s[j]-a[i]*(i-j))}$。${f[i]}$表示将前${i}$个数修改，并且第${i}$个数保持不变的最小费用；${s[i]}$表示前缀和；${a[i]}$表示第${i}$个数的值。
考虑优化。斜率式：${-a[i]*j+f[i]=(f[j]-s[j])+s[i]-a[i]*i}$。
然而我们发现斜率${-a[i]}$并不是单调的，所以就不能够直接取单调队列队首的元素了，那怎么办呢？只好在队列中二分了，二分的过程很好理解，详情见代码。
以上作废，我在说什么鬼话→_→，${-a[i]}$显然是单调的。。
再附张图，这次的单调队列里面的点构成的图形有点鬼。。竟然是个类似于反比例函数的东西→_→
细节
记得开long long。。。
代码
// poj3709
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 1ll<<60
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=500010;
LL a[maxn],f[maxn],s[maxn];
int n,K,q[maxn]; bool cmp(int a,int b) {
return a>b;
}
double slope(int x,int y) {
return (double)((f[y]-s[y])-(f[x]-s[x]))/(double)(y-x);
}
int main() {
int T;scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&K);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n,cmp);
for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
for (int i=1;i<=n;i++) f[i]=inf;
int l=1,r=1;q[1]=0;
for (int i=K;i<=n;i++) {
while (l<r && slope(q[l],q[l+1])<-a[i]) l++;
f[i]=f[q[l]]+s[i]-s[q[l]]-a[i]*(i-q[l]);
while (l<r && slope(q[r-1],q[r])>slope(q[r],i-K+1)) r--;
q[++r]=i-K+1;
}
printf("%lld\n",f[n]);
}
return 0;
}
代码（强行二分）
// poj3709
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 1e18
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=500010;
LL f[maxn],s[maxn],a[maxn];
int q[maxn],n,K; double slope(int x,int y) {
return (double)((f[y]-s[y])-(f[x]-s[x]))/(double)(y-x);
}
int find(int l,int r,LL x) {
int res=l;
while (l<=r) {
int mid=(l+r)>>1;
if (mid<r && x>slope(q[mid],q[mid+1])) l=mid+1,res=mid;
else if (mid>l && x<slope(q[mid-1],q[mid])) r=mid-1,res=mid;
else return mid;
}
return res;
}
bool cmp(LL a,LL b) {
return a>b;
}
int main() {
int T;scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&K);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n,cmp);
for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
for (int i=1;i<=n;i++) f[i]=inf;
int l=1,r=1;q[1]=0;
for (int i=K;i<=n;i++) {
int x=find(l,r,-a[i]);
f[i]=f[q[x]]+s[i]-s[q[x]]-a[i]*(i-q[x]);
while (l<r && slope(q[r-1],q[r])>slope(q[r],i-K+1)) r--;
q[++r]=i-K+1;
}
printf("%lld\n",f[n]);
}
return 0;
}