HDU6438 Buy and Resell

前言

今天的速度训练,可刺激了…

题目描述

分析

问题可以转化为:有N个点,每个点有权值A_i。找出tot个点对(i,j),满足i< j,且A_i< A_j(当然一个点不能重复出现在多个点对中),使得\sum A_j-A_i最大,并且在这一前提下tot尽可能小。
考虑对于一个点,我们可以将它与它前面还未匹配的权值最小点匹配。但这样会带来问题,可能一个点它与后面的点匹配更优,但是它却已经被前面不优的点匹配了。这时候我们可以增加一个反悔的操作,就是在点匹配后(也就是商品已经被resell了),如果有更优的方式,那就再把它买回来(可以叫rebuy…),再卖出去,这样利润仍然是不变的。当然为了让tot最小,这两个操作是可以合并为一个操作的,那么我们不妨这时统计一下,判断是这样的情况就把tot减一下。
我们用一个小根堆维护当前点以前的可匹配点的权值,另外用一个map来统计这个点是否是被resell了即可。

参考程序

关于小根堆,若使用STL priority_queue的话,还是那个问题,自定义comparer的时候要反过来,不是用std::less,而是std::greater。

#include <cstdio>
#include <queue>
#include <map>
#include <functional>   // for std::greater
#include <vector>

int N, T;

void solve();

int main() {
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

void solve() {
    scanf("%d", &N);
    std::priority_queue<int, std::vector<int>, /* 这个vector作底层容器好像是必选的...*/ std::greater<int> > Heap;
    std::map<int, int> Mp;
    long long ans = 0;
    int tot = 0;
    for (int i = 0, Ai, prv; i < N; i++) {
        scanf("%d", &Ai);
        if (!Heap.empty() && Heap.top() < Ai) {
            ans += Ai - (prv = Heap.top()), Heap.pop();     // 直接累加到ans
            Heap.push(Ai);  // 放一个反悔用的
            if (Mp[prv]) --tot, --Mp[prv];
            ++tot, ++Mp[Ai];
        }
        Heap.push(Ai);  // 放一个匹配用的,也就是说如果上面的if进去了这个点会被放入两次:一个反悔一个匹配,缺一不可
    }
    printf("%lld %d\n", ans, tot << 1);
}

总结

这道题贪心加上反悔的操作十分巧妙,类似于网络流中的反向流。也算是又多见了一种套路。

About The Author

发表评论

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