题解：B4223 [常州市赛 2024] 早起的鸟儿有虫吃

· · 题解

题目传送门

题意

丛林里有 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;
}

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