一、题意

某个城市有n个湖，每个湖初始装满水。
在接下来的m天，每天要么不下雨，要么会恰好往一个湖里下暴雨。
若下暴雨时，该湖已经装满水，则会发生水灾。
你是一条神龙，你可以在不下雨的日子里喝光一个湖的水（也可以不喝）。
给出接下来m天是否下雨以及会往哪些湖下暴雨，为了不引起水灾，你应该在不下雨的那几天里如何喝水？

二、解析

先来分析一下，是否会存在下暴雨时湖里正好没水的情形呢？答案是不会，因为n个湖初始都是装满水的，而我们并不会闲着没事干去喝水，因此我们总是在知道有一场暴雨会往一个装满水的湖里下时我们才会去喝干这个湖。

然后，如果一个装满水的湖在某一天被下了暴雨，那么我们必须在这一天之前喝干这个湖，而我们喝水的日期同时也要是在这个湖被装满水的日期之后，因此也就是，我们只要能找得到一个在 （这个湖被装满水的日期，暴雨降临到这个湖的日期） 这个区间之间的一个空闲的晴天来喝水，那么就可以阻止这一场水灾。

因此我们首先需要一个full_day[maxn]数组来存放每个湖上一次被装满水的日期，显然初始日期就是0；然后我们需要用一个set容器来存放在今天之前的所有晴天，这样我们在遍历日期时，若今天下雨，就只需要从set中找一个大于full_day[lake]的日子来喝水就好了，并把喝水事件记录到ans中，在这里我的ans使用一个map来存放的，当然也可以用其他方式。

为什么要用set呢？因为set是有序的，它能够在O(lgn)时间内实现找到大于上一次装满水的日期的最早的一个晴天（即lower_bound函数）。那为什么要找尽量早的那一个晴天呢？这里实际上是一个贪心策略，是为了尽可能地留下更晚一些的晴天日期给后面的雨天做准备（因为对于一个雨天来说，如果神龙喝水的日期在某一个晴天可行，那么在更晚的晴天喝水也总是可行的，因为这些晴天都是早于该下雨日期的）。

三、代码

#include <iostream>
#include <set>
#include <map>
using namespace std;
const int maxn = 1e6 + 5, maxm = 1e6 + 5;
int kase, n, m, full_day[maxn];
set<int> sunny_day;
map<int, int> ans;

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n >> m;
        fill(full_day, full_day + n + 1, 0);
        sunny_day.clear(), ans.clear();
        bool ok = 1;
        for(int i = 1, lake; i <= m; i ++) {
            cin >> lake;
            if(!ok) continue;
            if(lake) {
                auto iter = sunny_day.lower_bound(full_day[lake]);
                if(iter == sunny_day.end()) ok = 0;
                else full_day[lake] = i, ans[*iter] = lake, sunny_day.erase(iter);
            }
            else {
                sunny_day.insert(i);
                ans[i] = 0;
            }
        }
        if(!ok) cout << "NO" << endl;
        else {
            cout << "YES" << endl;
            bool first = 1;
            for(const auto& p : ans) {
                if(first) first = 0;
                else cout << " ";
                cout << p.second;
            }
            cout << endl;
        }
    }
}

四、归纳

  • 想清楚思路再动手敲代码
  • 通过set来实现对某些“动态数据”的二分查找是十分方便的，因为：
    • 有专门的函数可以直接调用：s.lower_bound(val)
    • 可以方便的增加、删除某些数据：s.insert(val)、 s.erase(iter)
    • set的所有操作都是O(lgn)级别的，不容易超时
  • 看到10^6的数据量时，不要老想着用O(n)的算法，因为也有可能需要的算法是O(nlgn)的