题解 P7594 【Clear Up】(贪心,模拟)

考场降智,对于带 0 的数据打了一个不知道是什么鬼东西的算法,还调挂了(


对于这些方块,我们把它们看成是 \(n\) 个平面上的点 \((i,a_i)\),那么样例 \(1\) 就长这样:

题解 P7594 【Clear Up】(贪心,模拟)

样例 \(2\) 就长这样:

题解 P7594 【Clear Up】(贪心,模拟)

我们发现就可以转换为这样一个问题:找到若干对直线 \(y1_i= x +b1_i\) 和 \(y2_i=-x +b2_i\),并使得 \(\sum (b1_i+b2_i)\) 最小(即截距之和最小),最后答案就是:
\(\sum \lceil\frac{(b1_i+b2_i)}{2}\rceil\) 。

长得有点像线性规划?(考场上就一直往线性规划上想,最后只有 45 pts),但其实没有那么复杂。

考虑这样一个结论:两对直线 \(y1_a,y2_a\) 和 \(y1_b,y2_b\) ,其中第一对直线交点 \(x_1\) 小于第二对直线交点 \(x_2\),若 \(y2_a\) 与 \(y1_b\) 的交点的 \(y\) 坐标 \(\geq 0\),则这两对直线可以合并成一对直线 \(y1_c=x+max(y1_a,y1_b),y2_c=-x+max(y2_a,y2_b)\)。

为什么?来感性理解一下,看这张图:

题解 P7594 【Clear Up】(贪心,模拟)

如图,两对黑色的直线(这里为了好看,画成射线)是原本的两队直线,红色(\(HR\) 和 \(HT\))的是合并后的一对直线,我们发现,这样的一对橙色线可以完美盖住两对黑色线的部分,还多盖住了标出的矩形的位置;并且,我们多画几个就会发现总是满足:\(\frac{b1_c+b2_c}{2}\leq \frac{b1_a+b2_a}{2}+\frac{b1_b+b2_b}{2}\),极限情况是交点在 \(x\) 轴上,此时 \(\frac{b1_c+b2_c}{2}= \frac{b1_a+b2_a}{2}+\frac{b1_b+b2_b}{2}\)。

那么只有有两对这样满足条件的直线,合并就一定更优。


具体做法有很多中,这里提供一个简单的做法:

我们发现可合并的直线对一定是相邻的,那么就可以这样:首先开一个栈记录从前向后的直线对。对于每个点,我们把它单独视为一个区间,两条直线分别为:\(y1_i=x+a_i-i\) 和 \(y2_i=-x+a_i+i\)。每新加入一个区间(点),从栈顶向下一直与可合并的区间合并,然后将合并完的新区间放到栈顶。最后扫一遍栈统计答案就行了。

代码:

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
inline int read(){
	rg int ret=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getchar();}
    return f?-ret:ret;
}
struct node{
	ll b1,b2;
}st[1000005],now;  //开栈。 
int n,top;
ll a[1000005],ans;  
inline node merge(node a,node b){
	node ret;
	ret.b1=max(a.b1,b.b1); ret.b2=max(b.b2,a.b2);
	return ret;
} //合并直线(区间)。 
signed main(){
	n=read();
	for(rg int i=1;i<=n;++i){
		a[i]=read(); now.b1=a[i]-i; now.b2=a[i]+i;  //将新加入的点视为一个已处理好的区间。 
		while(((st[top].b2+now.b1)>>1>=0)&&top) 
			now=merge(st[top--],now);   //不断 merge 并 pop。 
		st[++top]=now;    
	}
	while(top){
		if((st[top].b2+st[top].b1)&1) ans+=(st[top].b2+st[top].b1+1)>>1;
		else ans+=(st[top].b2+st[top].b1)>>1;
		--top;
	} //统计答案。 
	printf("%lld",ans);
	return 0;
}
上一篇:Allegro的优点与缺点


下一篇:(转)MapReduce二次排序