题解：UVA1623 神龙喝水 Enter The Dragon

Deepsick · 2026-11-09 21:31:34 · 题解

这能紫？？？那我要写个题解了。

按照题意，每次下雨操作都必须与一次喝水操作配对；并且，这次喝水必须在同一个湖的上一次下雨之后发生。因此，这次操作实际上规定了 a 序列中的一个区间，在每个区间内需要选择一个 0，并且这些 0 的位置互不相同。

考虑包含第一个 0 的区间。如果这样的区间存在，那么选取其中右端点最小的区间，把这个 0 分配给它，这样显然是不劣的。剩余的区间中，再对包含第二个 0 的区间进行处理，以此类推。

如果发现某个区间的左端点小于当前正在处理的 0，或者到最后也没有处理完全部区间，就说明无解。

在实现上，可以用优先队列维护当前考虑范围内的所有区间右端点，总复杂度 O(m\log m)。 ::::success[AC 代码]

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> b[1000001];//b[i] 就是以 i 为左端点的所有右端点构成的集合
int a[1000001],lst[1000001],ans[1000001];
priority_queue<int,vector<int>,greater<int> > q;
int main() {
    int T,n,m,i,j;
    cin>>T;while(T--) {
        cin>>n>>m;for(i=1;i<=n;i++) lst[i]=0;
        for(i=1;i<=m;i++) {b[i].clear();ans[i]=0;}
        for(i=1;i<=m;i++) {
            cin>>a[i];
            if(a[i]) {b[lst[a[i]]+1].push_back(i);lst[a[i]]=i;}
        }
        while(!q.empty()) q.pop();
        for(i=1;i<=m;i++) {
            for(j=0;j<b[i].size();j++) q.push(b[i][j]);
            if(!q.empty()&&q.top()<i) break;
            if(!a[i]&&!q.empty()) {ans[i]=a[q.top()];q.pop();}
        }
        if(!q.empty()) cout<<"NO\n";
        else {
            cout<<"YES\n";
            for(i=1;i<=m;i++) if(!a[i]) cout<<ans[i]<<' ';
            cout<<'\n';
        }
    }
}

::::