第二部分 基础算法 --> 第六章 贪心算法

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

贪心算法

1422：【例题1】活动安排

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

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

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

【输入样例】

4
1 3
4 6
2 5
1 7

【输出样例】

2

【题解】

#include
using namespace std;
const int N=1e3+10;
struct T{
    int s,f;
}t[N];
bool cmp(T a, T b){
    return a.f=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

下面的m行描述居民们的需要：B E T，0

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

【输入样例】

9 4
3 5 2
1 4 2
4 6 2
8 9 2

【输出样例】

5

【题解】

#include
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=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

【输出样例】

9950

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

【题解】

#include
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=1; j--){
            if(!vis[j]){
                vis[j]=1; flag=1; break;
            }
        }
        if(!flag){
            ans+=t[i].w;
        }
    }
    printf("%d\n", m-ans);
    return 0;
}