贪心题目总结,hdu 6301 Distinct Values

佚名 7年前 (2019-05-05) 随笔 1559人围观抢沙发百度已收录

一些经典贪心题目.

1. 给定$m$个区间, 求一个字典序最小的序列, 满足$m$个区间内数均不相同.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

hdu 6301 Distinct Values

2. 给定$m$个有序对$(a,b)$, 求构造一个$n$排列, 满足$m$个对中$a$均排在$b$前, 且$1$尽量靠前, 在$1$尽量靠前的前提下$2$尽量靠前,....以此类推

[HNOI2015]菜肴制作

1, 调整法.

先构造出一个可行解, 然后在不破坏解的可行性条件下, 不断调整到最优.

练习1. cf 913C

大意: n种汽水, 每种无限多, 第$i$种体积$2^{i-1}$, 花费$a_i$, 求总体积不少于$l$时的最少花费.

从第1种开始向后调整, 假设遍历到第$i$种, 若$i$的单价最低, 显然要把$i$之前选的调整为若干个$2^{i-1}$. 要注意可能存在之前的凑不够$2^{i-1}$的部分的总价少于$a[i]$, 也要调整.

#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n, l, a[N], c[N];

int main() {
    scanf("%d%d", &n, &l);
    REP(i,0,n-1) scanf("%d", a+i);
    int opt = 0;
    c[0] = l;
    REP(i,1,n-1) {
        if (a[i]<=((ll)a[opt]<<i-opt)) {
            int t = c[opt]>>i-opt;
            c[opt] -= t<<i-opt;
            c[i] += t;
            opt = i;
        }
        int t = 0;
        ll w = 0;
        PER(j,0,i-1) if (c[j]) {
            int cnt = min(c[j], (((1<<i)-t+(1<<j)-1)>>j)-1);
            t += cnt<<j, w += (ll)a[j]*cnt;
        }
        if (w>a[i]) {
            t = 0, ++c[i];
            PER(j,0,i-1) if (c[j]) {
                int cnt = min(c[j], (((1<<i)-t+(1<<j)-1)>>j)-1);
                c[j] -= cnt;
            }
        }
    }
    ll ans = 0;
    REP(i,0,n-1) ans+=(ll)a[i]*c[i];
    printf("%lld\n", ans);
}

练习2. cf 916B

大意: 求将n划分为k个2的幂的和, 且最大幂最小,字典序尽量大.

(1)先考虑将n划分为2的幂的和, 显然直接按二进制划分即可, 假设划分出$x$个数.

(2)考虑如何调整为k个, 注意到一个高次幂可以分为为两个更低次幂, 相当于对个数贡献加一, 所以只要$k\ge x$, 那么一定可以划分成功.

(3)要使最大幂最小, 我们可以在(2)中调整时先拆高次幂即可, 因为显然拆低次幂不会更优.

(4)考虑字典序最大, 也就是要保证个数和最大幂不变的前提下使字典序增加. 一个显然的方案是先选两个尽可能大的低次幂合并为高次幂, 为了使个数不变, 再选一个高次幂转化为两个低次幂.

总调整次数是$O(k)$的, 用stl的map实现, 复杂度就为$O(klogk)$

#include <iostream>
#include <cstdio>
#include <map>
#include <set>
using namespace std;

long long n;
int k;

int main() {
    scanf("%lld%d", &n, &k);
    int cnt = 0;
    map<int,int,greater<int> > s;
    for (int i=0; i<=62; ++i) if (n>>i&1) ++s[i],++cnt;
    if (k<cnt) return puts("No"),0;
    while (cnt<k) {
        auto t = s.begin();
        int tt = t->first;
        if (!--s[tt]) s.erase(t);
        s[tt-1] += 2;
        ++cnt;
    }
    set<int,greater<int> > r;
    int mx = s.begin()->first;
    for (auto t:s) if (t.first!=mx&&t.second>=2) { 
        r.insert(t.first);
    }
    while (r.size()) {
        int x = *r.begin();
        ++s[x+1], s[x]-=2;
        if (s[x]<2) r.erase(x);
        if (x+1!=mx&&s[x+1]>=2) r.insert(x+1);
        if (!s[x]) s.erase(x);
        auto t = --s.end();
        int tt = t->first;
        if (tt==x+1) {
            --s[x+1], s[x]+=2;
            break;
        }
        if (--s[tt]<2&&r.count(tt)) r.erase(tt);
        if (!s[tt]) s.erase(tt);
        s[tt-1] += 2, r.insert(tt-1);
    }
    puts("Yes");
    for (auto t:s) {
        while (t.second--) printf("%d ", t.first);
    } puts("");
}