第二部分基本算法 --> 第 6 章贪婪算法

最编程 2024-06-02 07:58:33

...

贪心算法
- 1422：【例题1】活动安排
- 1423：【例题2】种树
- 1426：【例题5】智力大冲浪

贪心算法

1422：【例题1】活动安排

【题目描述】
设有 n 个活动的集合 E={1,2,…,n}，其中每个活动都要求使用同一资源，
如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi,且 si<fi。
如果选择了活动 i，则它在半开时间区间 [si,fi) 内占用资源。
若区间 [si,fi) 与区间 [sj,fj) 不相交, 则称活动 i 与活动 j 是相容的。
也就是说，当 si ≥fj 或 sj ≥fi 时，活动 i 与活动 j 相容。
选择出由相互兼容的活动组成的最大集合。

【输入】
第 1 行一个整数 n(n≤1000)，接下来 n 行，每行两个整数 si 和 fi。

【输出】
输出尽可能多的互相兼容的活动个数。

【输入样例】

【输出样例】

【题解】

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct T{
    int s,f;
}t[N];
bool cmp(T a, T b){
    return a.f<b.f;
}
int main(){
    int n, cnt=1; scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d%d", &t[i].s, &t[i].f);
    }
    sort(t, t+n, cmp);
    int end=t[0].f;
    for(int i=1; i<n; i++){
        if(t[i].s>=end){
            cnt++;
            end = t[i].f;
        }
    }
    printf("%d", cnt);
    return 0;
}

1423：【例题2】种树

【题目描述】
现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，*要求每一住户门口种些树。
门口路边的地区被分割成块，并被编号成 1..N。
每个部分为一个单位尺寸大小并最多可种一棵树。
每个居民房子门前被指定了三个号码B，E，T。
这三个数表示该居民想在 B 和 E 之间最少种 T 棵树。
当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以 T ≤E-B+l。
居民们想种树的各自区域可以交叉。
你的任务是求出能满足所有要求的最少的树的数量，尽量较少*的支出。

【输入】
第一行包含数据N，M，区域的个数 (0<N≤30000)，房子的数目 (0<m≤5000)；

下面的m行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

【输出】
输出一个数，为满足所有居民的要求，所需要种树的最少数量。

【输入样例】

【输出样例】

【题解】

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
bool used[N];
struct T{
    int s,f,v;
}t[N];
bool cmp(T a, T b){
    return a.f<b.f;
}
int main(){
    int n,m,ans=0; scanf("%d%d", &n, &m);
    for(int i=0; i<m; i++){
        scanf("%d%d%d", &t[i].s, &t[i].f, &t[i].v);
    }
    sort(t, t+m, cmp);
    for(int i=0; i<m; i++){
        int cnt=0;
        for(int j=t[i].s; j<=t[i].f; j++){
            if(used[j]) cnt++;
        }
        if(cnt>=t[i].v) continue;
        for(int j=t[i].f; j>=t[i].s; j--){
            if(!used[j]){
                used[j]=1; cnt++; ans++;
            }
            if(cnt==t[i].v) break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

1426：【例题5】智力大冲浪

【题目描述】
小伟报名参加*电视台的智力大冲浪节目。
本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者 m 元。
先不要太高兴！因为这些钱还不一定都是你的。
接下来主持人宣布了比赛规则：
首先，比赛时间分为 n 个时段 (n≤500)，它又给出了很多小游戏，
每个小游戏都必须在规定期限 ti 前完成 (1≤ti≤n)。
如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱 wi，wi 为自然数，
不同的游戏扣去的钱是不一样的。
当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。
主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。
作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！
注意：比赛绝对不会让参赛者赔钱!

【输入】
输入共 4 行。
第一行为 m，表示一开始奖励给每位参赛者的钱；
第二行为 n，表示有 n个小游戏；第三行有 n 个数，分别表示游戏 1～n 的规定完成期限；
第四行有 n 个数，分别表示游戏 1～n 不能在规定期限前完成的扣款数。

【输出】
仅 1 行。表示小伟能赢取最多的钱。

【输入样例】

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

【输出样例】

【数据范围】n≤500，1≤ti≤n

【题解】

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
bool vis[N];
struct T{
    int t,w;
}t[N];
bool cmp(T a, T b){
    if(a.w!=b.w) return a.w>b.w;
    return a.t<b.t;
}
int main(){
//    freopen("data.in", "r", stdin);
    int m,n; scanf("%d%d", &m, &n);
    for(int i=0; i<n; i++) scanf("%d", &t[i].t);
    for(int i=0; i<n; i++) scanf("%d", &t[i].w);
    sort(t, t+n, cmp);
    int ans=0;
    for(int i=0; i<n; i++){
        bool flag=0;
        for(int j=t[i].t; j>=1; j--){
            if(!vis[j]){
                vis[j]=1; flag=1; break;
            }
        }
        if(!flag){
            ans+=t[i].w;
        }
    }
    printf("%d\n", m-ans);
    return 0;
}

原文地址：https://www.cnblogs.com/hellohebin/p/16044041.html

上一篇：缓存插件 TpCache Magic Edition - Hoshizawa V Club

下一篇： radius挑战认证+对接华为防火墙实现SSLvpn+钉钉双因素认证2

第二部分基本算法 --> 第 6 章贪婪算法

贪心算法

1422：【例题1】活动安排

1423：【例题2】种树

1426：【例题5】智力大冲浪

数学建模算法与应用》第 6 章微分方程及其解的建模

[代码随机化第 30 天] 贪婪算法第 04 部分

算法打分表：第 11 章图论第 10 部分

使用MATLAB粒子群算法解决多目标优化问题 - 包含详细Matlab源代码与第441期刊登示例 - 第二部分：源代码详解

操作系统_清华大学(向勇陈宇)-笔记-第6章-页面替换算法