题解：P11104 [ROI 2023] 监控 (Day 1)

思路：

仔细分析，很明显我们横向移动和纵向移动是互不影响的，那么我们就可以把横向和纵向分开来分析，这种将互不相干的几个量分离开的思想不仅在奥赛中，在文化课中也有广泛应用。

注意

$\min _h$ 和 $\min _w$ 就是最小间距。
在找 $cnt_h$ 和 $cnt_w$ 时，我们是通过对比当前点距边缘最小值与当前最小值。
$\min$ 的优先级高于 $cnt$ 。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+5;
inline void read(int &a){
	char ch;int f=1,k=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	a=k*f;
}
int h,w,k,min_h,min_w,cnt_h,cnt_w;
int x[N],y[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);	
	read(h),read(w),read(k);
	for(int i=1;i<=k;i++)
		read(x[i]),read(y[i]);
	
	sort(x+1,x+1+k);sort(y+1,y+1+k);
	min_h=x[k]-x[1]+1;min_w=y[k]-y[1]+1;
	
	for(int i=1;i<k;i++){
		if(h-(x[i+1]-x[i])+1<min_h){
			min_h=h-(x[i+1]-x[i])+1;
			cnt_h=min(min(x[i],h-x[i]),min(x[i+1],h-x[i+1]+1));
		}else if(h-(x[i+1]-x[i])+1==min_h)
			cnt_h=min(cnt_h,min(min(x[i],h-x[i]),min(x[i+1],h-x[i+1]+1)));
		
		if(w-(y[i+1]-y[i])+1<min_w){
			min_w=w-(y[i+1]-y[i])+1;
			cnt_w=min(min(y[i],w-y[i]),min(y[i+1],w-y[i+1]+1));
		}else if(w-(y[i+1]-y[i])+1==min_w)
			cnt_w=min(cnt_w,min(min(y[i],w-y[i]),min(y[i+1],w-y[i+1]+1)));
	}
	cout<<min_h*min_w<<' '<<cnt_h+cnt_w;
	return 0;
}

题解：P11104 [ROI 2023] 监控 (Day 1)

文章操作

思路：

注意

Code

相关推荐

评论

题解：P11104 [ROI 2023] 监控 (Day 1)