自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 22:46:19，当前版本为作者最后更新于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;
}