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

zengzidi · 2025-10-29 15:24:37 · 题解

因为最后的矩形的大小只受最上、最下的 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 在最右边，下标和讲解的有些不同）。

#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;
}