自动搬运

查看原文

来自洛谷，原作者为

	H17 *　*

搬运于2025-08-24 22:32:51，当前版本为作者最后更新于2023-10-01 16:12:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

其实就是告诉你边长求覆盖之后的总面积。

只需要维护 $i$ 这么高的地方多宽即可。

$70$ 分代码

//-O2
#include<bits/stdc++.h>
using namespace std;
unsigned int n,x,y,a[10000001];
unsigned long long ans;
int main(){
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		x/=2,y/=2;//其实只要维护一个角的
		int idx=upper_bound(a+1,a+n+1,y,greater<int>())-a;
		for(int i=idx;i<=x;i++)
			a[i]=max(a[i],y);//全部记录
	}
	for(int i=1;i<=10000000;i++)
		ans+=a[i];
	ans*=4;
	cout<<ans;
	return 0;
}

优化

其实分析下读入的时候需要把 $idx \to x$ 全扫一遍，比较消耗时间。

因为我们去掉了 $\frac{3}{4}$ 所以矩形一定是通到底的，所以只把他最高的地方记录上，然后往下的都和上一层取 $\max$ 然后一直到最底下（我知道很难说清楚，具体看代码）。

代码

#include<bits/stdc++.h>
using namespace std;
unsigned int n,x,y,a[10000001];
unsigned long long ans;
int main(){
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		x/=2,y/=2;
		a[x]=max(a[x],y);//把最上面记录
	}
	for(int i=10000000;i;i--){
		a[i]=max(a[i],a[i+1]);//和上面层比较
		ans+=a[i];
	}
	cout<<ans*4;
	return 0;
}