自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:17:57，当前版本为作者最后更新于2025-07-21 21:32:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意

丛林里有 $n$ 只鸟，每个位置都有 $1$ 只虫子，第 $i$ 只鸟在第 $x_i$ 行，$y_i$ 列。$x=1$ 时鸟向下飞，$y=1$ 时鸟向右飞，如果到达了一个已经没有虫子的格子这只鸟会停止在这个格子中。求每只鸟吃了多少只虫子。
测试数据保证 $x_i=1$ 或 $y_i=1$，并且在 $(1,1)$ 的位置没有鸟，所有的鸟在任意时刻的位置互不相同。

思路

十年 OI 一场空，不开long long 见祖宗！！！

我们用 $dir_i$ 记下第 $i$ 只鸟的方向，如果向下就为 $1$，如果向右就为 $0$。由于题目中鸟儿不可能在同一位置，且向下的 $x=1$，向右的 $y=1$，所以不会出现在同一行同时向右或者在同一列同时向下的。这样我们可以知道如果经过虫子被吃的地方那么肯定是不同方向的鸟吃掉的。此时，我们还要判断鸟 $j$ 是不是在鸟 $i$ 经过之前经过的（这里要根据方向做出不同判断，见代码）。最后更新答案，因为遇见没虫子的地方就停下，所以只需要比每次遇见没虫子的地方谁离出发点最近并用 $ans$ 记录下来就行啦。$ans$ 记得初始化为 $w$，毕竟 $ans$ 不可能大于 $w$。

十年 OI 一场空，不开long long 见祖宗！！！

代码

#include <bits/stdc++.h>
using namespace std;
int n, x[4], y[4], dir[4];
long long w, ans;
int main()
{
    scanf("%d%lld", &n, &w);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &x[i], &y[i]), dir[i] = x[i] == 1;
    for (int i = 1; i <= n; i++)
    {
        ans = w;
        for (int j = 1; j <= n; j++)
            if (i != j)
            {
                if (dir[i] && !dir[j] && y[i] < x[j])
					ans = min(ans, (long long)(x[j] - 1));
    			if (!dir[i] && dir[j] && x[i] < y[j])
					ans = min(ans, (long long)(y[j] - 1));
			}
        printf("%lld\n", ans);
    }
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。
题目传送门