NOIP 贪心训练

发表于 | 分类于 | | + s

第1题 CF 867E

CF 867E
题意：考虑股票市场，一共有$n$天。对于第$i$天，B君知道股票的价格是每单位$a_i$元
在每一天，可以选择买入一个单位的股票，卖出一个单位的股票，或者什么都不做。
刚开始有无穷多的钱，但是没有任何股票。
问$n$天之后最多可以赚多少钱。

解：用大根堆维护。从左往右扫，每次扫到一个数如果不大于当前堆的根，那么直接插。否则就先买(根和当前值)，然后再插两个当前值到堆里。相当于这次卖是一个中转点，不一定最终在这里卖。所以在后面如果有更优解那么将会继承中转点的值，也就是返回思想。

知识点：贪心思想可以用返回、中转点思想。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, t;
    LL ans = 0;
    priority_queue<int, vector<int >, greater<int > > q;

    void clean() {
    }
    int solve() {
        scanf("%d", &n);
        for (int x, i = 1; i <= n; ++i) {
            scanf("%d", &x);
            if (!q.empty() && x > q.top()) {
                ans += (LL)x - (LL)q.top();
                q.pop(); q.push(x);
            }
            q.push(x);
        }
        cout << ans;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

第2题 Bzoj 4198

Bzoj 4198
题意：多叉哈夫曼树。
解：按照二叉树方法贪心是错的，最后在根节点会出现节点不够用的情况。所以我们可以修改一下，将下面的节点移到上面。具体是加一堆0点以至于$(n-1) \mod (k-1)=0$(画图分析)。对于第二问，贪心最小合并次数的合并即可，

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    struct data {
        LL val, tms;
        bool operator < (const data &rhs) const {
            if (val == rhs.val) return tms > rhs.tms;
            return val > rhs.val;
        }
    };

    LL n, k, ans, maxd;
    priority_queue<data > q;

    void clean() {
        maxd = ans = 0;
    }
    int solve() {
        clean();
        scanf("%lld%lld", &n, &k);
        for (LL x, i = 1; i <= n; ++i) scanf("%lld", &x), q.push((data){x, 0});
        while ((n - 1) % (k - 1) != 0) q.push((data){0, 0}), ++n;
        for (LL i = 1; i <= (n - 1) / (k - 1); ++i) {
            LL tmp1 = 0, tmp2 = 0;
            for (LL j = 1; j <= k; ++j) {
                data p = q.top(); q.pop();
                tmp1 += p.val, tmp2 = max(tmp2, p.tms);
            }
            maxd = max(maxd, tmp2 + 1);
            ans += tmp1;
            q.push((data){tmp1, tmp2 + 1});
        }
        printf("%lld\n%lld\n", ans, maxd);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------