题解：AT_abc391_d [ABC391D] Gravity

da_ke · 2025-02-02 10:42:23 · 题解

像流星划过夜空，转瞬即逝的梦。

在平面直角坐标系中，有 N 颗流星（shooting_star）划过，第 i 颗的初始坐标（第 0 时刻坐标）为 (X_i,Y_i)。保证 1 \leq X_i\leq W。

每一个单位时刻，流星按如下规则运动：

如果底部是满的既 (1,1),(2,1),\cdots,(W,1) 的位置上都有流星，那么这些流星在这个时刻末全部消失；否则底部的流星不动。
其余不在底部的流星向下移动一个单位。

在看流星的 fyy 想问妳 Q 个问题：询问第 A_i 个流星在 T_i 时刻末是否存在。

妳非常聪明，很快注意到 Q 很大，不可能一个一个处理，妳打算对于每一个流星，计算它消失的时刻。

如何计算每一个流星消失的时刻？妳很快发现流星消失是一轮一轮的。

考察横向和竖向的变化：

横向：妳发现一轮消失的流星总是每一列中最低的一个。
纵向：妳发现每一列中，低的流星总不会影响高的流星的运动状态。

以上是一些感性认识，我们现在转化为形式化语言。

考虑将流星按列放进优先队列。具体的，初始 (X_i,Y_i) 放进 q_{X_i}。其中 q_1,q_2,\cdots,q_W 为 W 个小根堆（优先队列）。
取 q_1,q_2,\cdots,q_W 的队首。
- 如果某个队列空了，那么以后的流星（包括这一轮）永不消失。
- 否则取 q_1,q_2,\cdots,q_W 的队首 y 坐标的最大值为这一轮所有流星的消失时间 T_{max}（注意临界问题，如果一个时刻 T\ge T_{max} 那么这一轮的流星都在 T 时刻消失过了，注意能取等号）。
- 将所有队首出队。
不断执行操作 2，直至存在一个空队。

然后代码是很简单的，据笔者所知很多人这道题都死于细节。笔者自认为自己的代码细节很少好理解。

const int fyy=0;

int main()
{
    int N,W;
    cin>>N>>W;
    vector<priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>> q(W+1);
    vector<int> ans(N+1,(int)1e9+24);
    rep(i,1,N)
    {
        int X,Y;
        cin>>X>>Y;
        q[X].push({Y,i});
    }
    bool zxq=1; // 张修齐：是否可进行下一轮
    while(zxq)
    {
        int _max=fyy;
        rep(i,1,W)
        {
            if(q[i].empty())
            {
                zxq=fyy;
                break;
            }
            _max=max(_max,q[i].top().first);
        }
        if(!zxq) break;
        rep(i,1,W)
        {
            ans[q[i].top().second]=_max;
            q[i].pop();
        }
    }
    int Q;
    cin>>Q;
    while(Q--)
    {
        int T,A;
        cin>>T>>A;
        if(T>=ans[A])
            cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}

// 路虽远行则将至，事虽难做则必成。

AC 记录：https://atcoder.jp/contests/abc391/submissions/62291264

流星姐姐珂愛喵~