T183637 变异距离

T183637 变异距离

传送门

题意简明, 不做解释
个人觉得抛开数据和读入, 这题还不错。


题解

如果你没有看错题目的话,\(O(nlogn)\)的做法还是很好想到的。
那么问题来了, o(n)做法呢。
既然按y排序会超时, 那么为什么不试试x呢, 这题x只给到了1e6, 显然是要用桶排的。

n = read();
int s=N, t=0;
for(int i=1; i<=n; i++){
	int a=read()+D, b=abs(read());
	flag[a] = max(flag[a], b);
	s=min(s, a), t=max(t, a);
}

n=0;
for(int i=s; i<=t; i++)
	if(flag[i]) x[++n]=i-D, y[n]=flag[i];

把所有点按x排序后,我们再来考虑。
对于每一个点a,我们考虑让它向右(即x比它大的点)匹配另一个点b, 并且让\(Ya<Yb\), 也就是让a的y成为较小的那个的最大值值。

现在我们来看一个单调性。

假如现在对于一个点a, 这个点的y值比之前已经匹配过的一个点c的y小
T183637 变异距离
假设a与某一个点匹配成为了最大值, 那么c也一定能成为最大值。(可自己证明
所以我们可以不考虑a
T183637 变异距离
这样我们每次匹配的点的y就是单调的了。

那么进一步, 我们怎么知道当前的点(记为a)要和哪个点(记为b)匹配呢。
首先, 为了使得\(|xa - xb|\)最大, 我们要尽可能向右匹配
然后, 为了让\(Y_a\)成为较小的那个,要保证 \(Y_b > Y_a\)
说人话:对于每个点a, 要找到右边第一个大于\(Y_a\)的点(仔细想
然后由于每次匹配的点的y是单调的。
所以第一个大于Ya的点也是单调的
从右边扫过来即可。
时间复杂度\(O(n)\)
(不懂可以看代码或仔细想

为什么要扫两遍呢?因为不一定是向右,还可能向左

void solve(){
	ans = 0;
	for(int i=1, j=n; i<=n; i++){
		while(j>=1 && y[j]<y[i]) j--;
		if(i > j) break;
		ans = max(ans, 1ll*abs(x[i]-x[j])*y[i]);
	} 
	for(int i=n, j=1; i>=1; i--){
		while(j<=n && y[j]<y[i]) j++;
		if(i < j) break;
		ans = max(ans, 1ll*abs(x[i]-x[j])*y[i]);
	} 
	printf("%lld\n", ans);
}
上一篇:记我的oi生涯


下一篇:Winform中实现读取xml配置文件并动态配置ZedGraph的RadioGroup的选项