算法竞赛进阶指南-0x07基本算法-贪心

防晒

题意:
蓝书P42

Solution:
将所有奶牛按照 minSPF 从大到小的顺序排序,然后依次考虑每头奶牛;
对于每头奶牛,扫描当前所有能用的防晒霜,选择 SPF 值最大的防晒霜来用;

Code:

int n, m;
P a[2505];
map<int, int> mp;

int main(){
    __;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)    cin >> a[i].fi >> a[i].se;
    for(int i = 1; i <= m; i ++){
        int x, y;
        cin >> x >> y;
        mp[x] += y;
    }
    sort(a + 1, a + n + 1);
    mp[0] = mp[1001] = n;
    int ans = 0;
    for(int i = n; i >= 1; i --){
        auto k = mp.upper_bound(a[i].se);
        k --;
        if(k->first >= a[i].fi){
            ans ++;
            if(-- k->second == 0)   mp.erase(k);
        }
    }
    cout << ans << endl;
    return 0;
}

畜栏预定

题意:
蓝书P43

Solution:
将所有牛按开始吃草的时间排序;
用小根堆维护当前所有畜栏的最后一头牛的吃草结束时间;
如果当前的牛可以安排在堆顶的畜栏中,则将其安排进去,否则就新建一个畜栏;

Code:

int n;
pair<P,int> v[50005];
priority_queue<P, vector<P>, greater<P> > q;
int ans[50005];

int main(){
    __;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> v[i].fi.fi >> v[i].fi.se;
        v[i].se = i;
    }
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; i ++){
        if(q.empty() || q.top().fi >= v[i].fi.fi){
            pair t = {v[i].fi.se, q.size() + 1};
            ans[v[i].se] = t.se;
            q.push(t);
        }
        else{
            pair t = q.top();
            q.pop();
            t.fi = v[i].fi.se;
            ans[v[i].se] = t.se;
            q.push(t);
        }
    }
    cout << q.size() << endl;
    for(int i = 1; i <= n; i ++){
        printf("%d\n", ans[i]);
    }
    return 0;
}

雷达设备
蓝书P43

题意:

Solution:
将所有小岛转化成区间后,问题转化为:给定 n 个区间,在 x 轴上选择尽量少的点,使得所有区间至少包含一个点。

将所有区间按右端点从小到大排序;
依次考虑每个区间:
- 如果当前区间包含最后一个选择的点,则直接跳过;
- 如果当前区间不包含最后一个选择的点,则在当前区间的右端点的位置选一个新的点;

Code:

int n;
double d;
pair<double, double> v[1005];

int main(){
    __;
    cin >> n >> d;
    bool f = false;
    for(int i = 1; i <= n; i ++){
        double x, y;
        cin >> x >> y;
        if(y > d)   f = true;
        v[i] = {x + sqrt(d * d - y * y), x - sqrt(d * d - y * y)};
    }
    if(f)   puts("-1");
    else{
        sort(v + 1, v + n + 1);
        double pre = -3e9;
        int ans = 0;
        for(int i = 1; i <= n; i ++){
            if(v[i].se > pre + eps){
                ans ++;
                pre = v[i].fi;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

国王游戏

题意:
蓝书P44

Solution:
直接将所有大臣按左右手上的数的乘积从小到大排序,得到的序列就是最优排队方案。
证明

Code:

int n;
P v[1005];

void output(vector<int> a){
    for(int i = a.size() - 1; i >= 0; i --){
        cout << a[i];
    }
    cout << endl;
}

vector<int> mul(vector<int> a, int b){
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size(); i ++){
        t += a[i] * b;
        c.pb(t % 10);
        t /= 10;
    }
    while(t)    c.pb(t % 10), t /= 10;
    return c;
}

vector<int> div(vector<int> a, int b){
    vector<int> c;
    bool f = false;
    int t = 0;
    for(int i = a.size() - 1; i >= 0; i --){
        t = t * 10 + a[i];
        int x = t / b;
        if(x || f){
            f = true;
            c.pb(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}


vector<int> two_max(vector<int> a, vector<int> b){
    if(a.size() > b.size()) return a;
    if(b.size() > a.size()) return b;
    if(vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend()))   return a;
    return b;
}


int main(){
    __;
    cin >> n;
    for(int i = 0; i <= n; i ++){
        int a, b;
        cin >> a >> b;
        v[i] = {a * b, a};
    }
    sort(v + 1, v + n + 1);

    vector<int> x(1, 1);
    vector<int> ans(1, 0);

    for(int i = 0; i <= n; i ++){
        if(i)   ans = two_max(ans, div(x, v[i].fi / v[i].se));
        x = mul(x, v[i].se);
    }
    output(ans);
    return 0;
}

给树染色

题意:
蓝书P45

Solution:
每次找出当前权值最大的非根节点,将其染色顺序排在紧随父节点之后的位置,然后将该点合并进父节点中,更新父节点的权值。直到将所有点都合并进根节点为止。

Code:

#include <bits/stdc++.h>
using namespace std;

int n, u;
int ans;
struct node{
    int s, num, fa;
    double avg;
}nodes[1005];


int find(){
    int res = 0;
    double s = 0;
    for(int i = 1; i <= n; i ++){
        if(i != u && nodes[i].avg > s){
            res = i;
            s = nodes[i].avg;
        }
    }
    return res;
}

int main(){
    cin >> n >> u;
    for(int i = 1; i <= n; i ++){
        cin >> nodes[i].s;
        nodes[i].num = 1;
        ans += nodes[i].s;
        nodes[i].avg = nodes[i].s;
    }

    for(int i = 1; i < n; i ++){
        int a, b;
        cin >> a >> b;
        nodes[b].fa = a;
    }

    for(int i = 1; i < n; i ++){
        int ver = find();
        int fver = nodes[ver].fa;
        nodes[ver].avg = -1;
        ans += nodes[ver].s * nodes[fver].num;
        for(int j = 1; j <= n; j ++){
            if(nodes[j].fa == ver)
                nodes[j].fa = fver;
        }
        nodes[fver].s += nodes[ver].s;
        nodes[fver].num += nodes[ver].num;
        nodes[fver].avg = (double)nodes[fver].s / nodes[fver].num;
    }
    cout << ans << endl;
    return 0;
}

点赞

发表评论

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