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

因为最后的矩形的大小只受最上、最下的

r

和最左、最右的

c

的影响。而向上、下走只影响

r

，向左向右走只影响

c

。所以其实可以把

r

和

c

拆开来讨论。

我们先处理如何让最后矩形的左右间距小。我们先把

c

先排序。

这张图中，

w=13

，其中

c_1=4

、

c_2=6

、

c_3=12

。

我们可以发现，现在这张图往左走

3

次或往右走

1

次对最后的矩形的左右间距大小没有影响。因为没有一个位置会走出单元格，去到对面。

一直向左走。设

c'

为现在各个图像所处的

c

坐标。

现在的左右距离为

c'_1-c'_2+1

，发现还可以表示成

w-(c_2-c_1)+1

。

我们继续往左走，当

2

又出现在右边时，可以发现，左右距离为

c'_2-c'_3+1=w-(c_3-c_2)+1=8

。

我们可以发现规律，当从左往右第

i

个图像出现在最右边时，左右间距为

w-(c_{i+1}-c_i)+1

，再把每一次计算的结果取最小值，即可得到左右最小的间距。求上下间距的方法类似。

我们现在还要求移动多少次。还是以左右为例。我们可以发现往左走，当

i

走到尽头再出现在最右边，需要

c_i

次。但

i

还可以直接往右走。往右走不一定要到尽头，只要让右边没有别的视频就行了，需要

w-c_{i+1}+1

次。所以移动次数是

\min(c_i,w-c_{i+1}+1)

。

最后是代码。（代码里面写的是

i-1

在最右边，下标和讲解的有些不同）。

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=1e5+5;
int h,w,k,n,r[maxn],c[maxn];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>h>>w>>n;
    for(int i=1;i<=n;i++)cin>>r[i]>>c[i];
    sort(r+1,r+1+n);
	sort(c+1,c+1+n); 
	int R=r[n]-r[1]+1,C=c[n]-c[1]+1;
	int u=0,s=0;
	for(int i=n;i>=2;i--)
	{ 
		if(R==r[i-1]+(h-r[i]+1))
		{
			s=min(s,min(h-r[i]+1,r[i-1]));
		}
		else if(R>r[i-1]+(h-r[i]+1))
		{
			R=r[i-1]+(h-r[i]+1);
			s=min(h-r[i]+1,r[i-1]);
		}
	}
	for(int i=n;i>=2;i--)
	{
		if(C==c[i-1]+(w-c[i]+1))
		{
			u=min(u,min(w-c[i]+1,c[i-1]));
		}
		else if(C>c[i-1]+(w-c[i]+1))
		{
			C=c[i-1]+(w-c[i]+1);
			u=min(w-c[i]+1,c[i-1]);
		}
	}
	cout<<R*C<<' '<<s+u;
    return 0;
}

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

文章操作

相关推荐

评论

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