专栏文章

题解 P9982

HHYdroKomide
P9982题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqs9n5t
此快照首次捕获于
2025/12/04 09:54
3 个月前
此快照最后确认于
2025/12/04 09:54
3 个月前
查看原文

题意：

给定一些点数轴上的整点 xix_i 和 a,ba,b，调整 yy 并最小化下式：
∑i=1n{a⋅(y−xi)if y>xib⋅(xi−y)if xi>y\sum_{i=1}^n \begin{cases}a\cdot (y-x_i) & \text{if} \ y>x_i \\ b\cdot(x_i-y)&\text{if}\ x_i>y\end{cases}

思路：

不难观察到原式单谷，关键是怎么证。
考虑最优解的点，设其左侧有 pp 个谷仓，右侧有 qq 个谷仓，自身位置有 kk 个谷仓。右移一个单位长度的贡献是 (p+k)⋅a−q⋅b(p+k)\cdot a-q\cdot b。左移一个单位长度的贡献是 (q+k)⋅b−p⋅a(q+k)\cdot b-p\cdot a。
显然，这两个值必然是正的。
考虑不断向左或向右移动，对于上述两个式子，每次经过谷仓后，第一项的系数会不断增加，第二项的系数会不断下降。即：贡献只会单调上升。
初始化每个位置左右的谷仓距离之和，对于每个点我们可以 O(1)O(1) 计算该位置的分数。二分或三分找最低点即可。
复杂度 O(m+qlog⁡m)O(m+q\log m)。

程序如下：

CPP
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2e5+5,M=1e6+5;
long long n,q,a,b,x[N],pre[M],pos[M];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&x[i]),x[i]++;
	sort(x+1,x+n+1);
	int fr=0,cur=1;
	for(int i=1;i<=x[n];i++){
		pre[i]=pre[i-1]+fr;
		while(x[cur]==i)cur++,fr++;
	}
	fr=0,cur=n;
	for(int i=x[n];i>=1;i--){
		pos[i]=pos[i+1]+fr;
		while(x[cur]==i)cur--,fr++;
	}
	pre[0]=pre[x[n]+1]=1e9;
	pos[0]=pos[x[n]+1]=1e9;
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&a,&b);
		long long l=1,r=x[n],ans;
		while(l<r){
			int mid=(l+r)>>1;
			long long curans=pre[mid]*a+pos[mid]*b;
			long long nxtans=pre[mid+1]*a+pos[mid+1]*b;
			if(nxtans<curans)l=mid+1;
			else r=mid;
		}
		printf("%lld\n",pre[l]*a+pos[l]*b);
	}
	return 0;
}

THE END

USACO 2024 Dec RP++.

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...