zoj 3508 – The War

这道题有点意思,是从 35XX 版里面挑选的 AC 最多的第二道题。 题目是这样的,有一堆武器重量是 w[1..m] (m <= 40000),有一堆士兵 s[1..n] (n <= 2500)。 每个士兵只能匹配重量在 s[i].min 和 s[i].max 之间 的武器,求最大匹配。

从数据规模上看,肯定是贪心。直接说结论: 对武器排序,从最轻的武器开始,那么如果这个武器总是匹配到当前可能匹配到的士兵中,s[i].max 最小那个,那么结果就是最优的。 具体证明不太想思考,读者有兴趣可以证明一下。

那么,我可以先对士兵的区间进行排序,然后构造一个优先队列 q; 从小到大遍历 w[i],q 中存放的是所有当前 w[i] >= s[j].min 的士兵 j 对应的 s[j].max; 每遍历一个 w[i],做以下操作: 1. 往后查看 s[j].min,对于每个 w[i] >= s[j].min,将 s[j].max 放入优先队列,直到 j==n 或者 w[i] < s[j].min; 2. 从 q 中取出所有 q.top() < w[i] 的值,因为这些区间已经匹配不到没用了; 3. 如果 q 还有,pop 一个出来进行匹配,结果数加一; 算法结束。

可以看到,做 w[] 的排序需要 O(mlog(m)),做 s[] 的排序需要 O(nlog(n)),遍历每个 w[i],s 的每个元素最多只进队列一次,出队列一次,每个进出队列需要 O(log(n)),因此这个遍历需要 O(mlog(n))。 因此算法的整体复杂度为 O(min{mlog(m), mlog(n), nlog(n)}),也就是小于 40000*log(40000),是可以很快搞定的。

实际上操作中,由于开始使用了 set 作为优先队列,吃了几个 wa,事实上起码应该采用 multiset,改了之后就 ac 了。 为了改善效率,后来把 multiset 改成 priority_queue 另作一版本,时间效率更高了(常数更低),该题榜上排到第三名。

// 3492409 2013-12-19 23:03:06 Accepted 3508 C++ 10 412 呆滞的慢板
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

int n, m, i, j, ans, s[2500], w[40000], x, y;
multiset<int> q;

int main() {

    while(scanf("%d%d", &n, &m) != EOF) {

        // input and pre-process.
        for(i = 0; i < n; ++i) {
            scanf("%d%d", &x, &y);
            s[i] = ((x<<16)|y);
        }
        sort(s, s+n);

        for(i = 0; i < m; ++i) scanf("%d", w+i);
        sort(w, w+m);

        // run the greedy process.
        ans = 0;
        q.clear();

        for(i = j = 0; i < m; ++i) {

            while(j < n && (s[j]>>16) <= w[i]) q.insert(s[j++]&0xFFFF);

            while(!q.empty() && *q.begin() < w[i]) q.erase(q.begin());

            if(!q.empty()) {
                q.erase(q.begin());
                ans += 1;
            }

        }

        printf("%d\n", ans);

    }

}

【转载请附】愿以此功德,回向 >>

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3508.html【zoj 3508 – The War】

发表评论

电子邮件地址不会被公开。 必填项已用*标注