P9205 题解

Night_sea_64 · 2023-04-10 21:05:07 · 题解

我们最终的目的，其实就是让每个正方形都包含比它小的正方形，并且也包含 (x_{\text{end}},y_{\text{end}})。

但是我们一开始所有正方形都包含比它小的正方形。而且我们需要最少步数。可证如果每个正方形都通过最少的移动使得包含 (x_{\text{end}},y_{\text{end}})，那么这些正方形一定会包含所有比它小的正方形。

于是我们只需要算出每个正方形需要包含 (x_{\text{end}},y_{\text{end}}) 的最少步数之和了。

#include<iostream>
#define int long long
using namespace std;
int n,fx,fy;
signed main()
{
    cin>>n>>fx>>fy;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(fx<x)cnt+=x-fx;//在左方
        else if(fx>x+i-1)cnt+=fx-(x+i-1);//在右方
        //cout<<i<<" "<<cnt<<endl;
        if(fy<y-i+1)cnt+=(y-i+1)-fy;//在下方
        else if(fy>y)cnt+=fy-y;//在上方
        //cout<<i<<" "<<cnt<<endl;
    }
    cout<<cnt<<endl;
    return 0;
}