【poj3709】 K-Anonymous Sequence

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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;

}