C++知识点总结(19)：高级贪心算法

高级贪心算法

一、P1803 活动安排
二、P1094 纪念品分组
三、村民打水
四、习题
彩蛋

一、P1803 活动安排

1. 审题

题目描述

春节快要到了，耶斯莫拉大酒店在最近几天要举办 $n$ 个活动，这些活动都需要使用酒店的大礼堂，而在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，酒店管理人员只好让一些活动放弃使用礼堂而使用其他小的餐厅。现在给出n个活动使用礼堂的起始时间 $begin_i$ 和结束时间 $end_i$ ( $begin_i < end_i \le 32767$ )，请你帮助酒店管理人员安排一些活动来使用礼堂，要求安排的活动尽量多。假设没有重新布置礼堂时间的消耗，即某个时间点完成活动的瞬间，就可以开始下一个活动。

输入描述

第一行一个整数 $n$ ( $\le 1000$ )；接下来的 $n$ 行，每行两个整数，第一个 $begin_i$ ，第二个是 $end_i$ ( $begin_i < end_i \le 32767$ )。

输出描述

输出最多能安排的活动个数。

样例1

输入

输出

提示

无

2. 思路

2.1 最优区间挑选方法

开始时间

不应该这么直接，因为开始时间的早晚会导致活动少，不是最优解。

所用时间

如果在两个活动执行区间内有一个更短时间的活动，则错过了几个活动，不是最优解。

结束时间

结束时间越早，说明后面剩余的连续时间越多
，是最优解。

2.2 分配时间方法

首先，一定要从一个区间开始遍历，因为如果这个区间包含了下个区间，那么选择这个区间不如选择下一个区间划算，选下个区间还能节省几个点来用于其他区间的选择。

2.3 排序方法

通过结束时间，从小到大进行排序（需要用到结构体 struct ）。

3. 参考答案

#include <iostream>
#include <algorithm>
using namespace std;

int n, rem, ans = 1;

struct Node
{
   
    int l, r;
}a[1005];

bool cmp(Node a, Node b)
{
   
    return a.r < b.r;
}

int main()
{
   
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
   
        cin >> a[i].l >> a[i].r;
    }
    
    sort(a+1, a+n+1, cmp);
    int rem = a[1].r;
    
    for (int i = 2; i <= n; i++)
    {
   
        if (a[i].l >= rem)
        {
   
            ans++;
            rem = a[i].r;
        }
    }
    
    cout << ans;
	return 0;
}

二、P1094 纪念品分组

1. 审题

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

输入文件 gift.in
共 $n + 2$ 行：
第一行包括一个整数 $w$ ，为每组纪念品价格之和的上限。
第二行为一个整数 $n$ ，表示购来的纪念品的总件数 $G$ 。
第 $3 n + 23 n + 2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

输出格式

输出文件 gift.out
一个整数，即最少的分组数目。

样例1

输入

输出

提示

$50\%$ 的数据满足： $1\le n\le15$
$100\%$ 的数据满足： $1\le n\le3\times10^4$ ， $80\le w\le200$

2. 思路

2.1 每组多少个方法

当和 $\le w$ 的时候，优先 $2$ 个一组。

2.2 搭配的方法

优先让危险的数字（越贵）找不危险的数字（越便宜），也就是大找小。
如果超过 $w$ 则优先让大的组成 $1$ 组。

3. 参考答案

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int w, n, cnt;
int num[30005];

int main()
{
   
    freopen("gift.in", "r", stdin);
    freopen("gift.out", "w", stdout);
    
    cin >> w >> n;
    for (int i = 1; i <= n; i++)
    {
   
        cin >> num[i];
    }
    
    sort(num+1, num+n+1);
    
    int i = 1, j = n;
    while (i <= j)
    {
   
    	// 贵的配便宜的 
        if (num[j] + num[i] <= w)
        {
   
            cnt++;
            j--;
            i++;
        }
        // 贵的单独一组 
        else
        {
   
            cnt++;
            j--;
        }
    }
    cout << cnt;
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}

三、村民打水

1. 审题

题目描述

在一个小村子里，生活着 $n$ 户人家。由于村里只有一口井，所以他们每天早上一户人家派一个人在这一口井前排队打水。由于每家的水桶大小不同，所以每个人的打水时间也不同。假如每个人打水的时间为 $T_i$ ，请你编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

输入描述

共两行，第一行为 $n$ ；第二行分别表示第 $1$ 个人到第 $n$ 个人每人的打水时间 $T_i$ ，每个数据之间有 $1$ 个空格。

输出描述

共两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

样例1

输入

10					
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
291.90

提示

$\le n \le 10^5$
$\le T_i \le 10^6$ ，不保证 $T_i$ 不重复
当 $T_i$ 重复时，按照输入顺序即可（sort 是可以的）

2. 思路

计算每个人的等待时间，并且累加得到总的等待时间 $an s$ 。对于第 $i$ 个人，他的等待时间为 $n-i) * t_i$ ，其中 $n$ 是总人数， $t_i$ 是第 $i$ 个人的打水时间。

3. 参考答案

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

int n;
double ans;

struct Node
{
   
    int idx;
    int t;
}person[100005];

bool cmp(Node a, Node b)
{
   
    if (a.t != b.t)
    {
   
        return a.t < b.t;
    }
    return a.idx < b.idx;
}

int main() 
{
   
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
   
	    person[i].idx = i;
	    cin >> person[i].t;
	}
	
	sort(person+1, person+n+1, cmp);
	
	for (int i = 1; i <= n; i++)
	{
   
	    ans += person[i].t * (n-i);
	    cout << person[i].idx << " ";
	}
	ans /= n;
	cout << endl << fixed << setprecision(2) << ans;
	return 0;
}

四、习题

1. 服务等待

1.1 审题

题目描述

小明新店开业，免费为顾客进行按摩服务，现在已经排了一个有 $n$ 个人的队伍，其中第 $i$ 个人需要 t[i] 分钟来服务，期间后面的人就要等着。如果一个人等待的时间大于了他被服务的时间，他就会失望，就会离开队伍。
你的任务是重排队伍，使失望的人尽量的少，并输出最多有多少个不失望的人。

输入描述

第 $1$ 行一个整数 $n$ ，表示队伍人数。
接下来 $n$ 行，每行一个整数，表示第i个人的服务时间 $t [i]$ 。

输出描述

输出一行，为一个整数，表示最多不失望的人数。

样例1

输入
5
15 
2 
1 
5 
3
输出
4

提示

$\le n \le 10^5，1 \le t[i] \le 10^3$

1.2 参考答案

#include <iostream>
#include <algorithm>
using namespace std;

int n, cnt, wait;
int t[100005];

int main()
{
   
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
   
        cin >> t[i];
    }
    
    sort(t+1, t+n+1);
    
    for (int i = 1; i <= n; i++)
    {
   
        if (wait <= t[i])
        {
   
            cnt++;
            wait += t[i];
        }
    }
    
    cout << cnt;
	return 0;
}

2. 春节糖果

2.1 审题

题目描述

春节快到了，王老师给同学们准备了春节糖果，让胡图图负责糖果的发放工作。王老师准备的不同糖果美味度不同，为使得各位同学所获得的糖果美味度相对均衡，图图需要把购来的糖果根据美味度进行分组，但每组最多只能包括两份糖果，并且每组糖果的美味度之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有糖果，图图希望分组的数目最少。由于胡图图比较糊涂，所以请你帮图图写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入描述

输入文件名 gift.in
共 $n + 2$ 行：
第 $1$ 行包括一个整数 $w$ ，为每组糖果美味度之和的上限。
第 $2$ 行为一个整数 $n$ ，表示购来的糖果的总件数。
第 $3 n + 2$ 行每行包含一个正整数 $p_i$ ( $\le p_i \le w$ )，表示所对应糖果的美味度。

输出描述

输出文件名 gift.out
仅一行，包含一个整数，即最少的分组数目。

样例1

输入

输出

提示

$50\%$ 的数据满足： $\le n \le 15$
$100\%$ 的数据满足： $\le n \le 3 \times 10^4, 80 \le w \le 200$

2.2 思路

将购来的糖果按照美味度从小到大进行排序。

使用双指针（尺取）来选择糖果，组成分组。

设置两个指针 $l$ 和 $r$ ，分别指向糖果数组的第一个和最后一个元素。

每次迭代中，判断左指针和右指针所指的糖果美味度之和是否小于等于给定的美味度上限 $w$ 。

如果是，表示可以将这两个糖果放在同一组内，我们将左指针向右移动一位，右指针向左移动一位。

如果不是，表示这两个糖果无法放在同一组内，我们只能将右指针向左移动一位继续成组。

在每次迭代中，无论是否能放入同一组内，我们都将分组数目 $c n t$ 自增。

当左指针超过右指针时，表示所有的糖果都已经处理完毕，此时 $c n t$ 的值为最少的分组数目。

这种算法通过贪心的策略，每次选择美味度最小和最大的糖果进行配对，以保证尽可能多的糖果被分组。同时，通过排序操作，使得每次选择到的糖果的美味度是当前剩余糖果中最小的，这样有利于后续的分组过程。

2.3 参考答案

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int w, n, cnt, sum;
int candies[30005];

int main()
{
   
    freopen("gift.in", "r", stdin);
    freopen("gift.out", "w", stdout);
    
    cin >> w >> n;
    for (int i = 1; i <= n; i++)
    {
   
        cin >> candies[i];
    }
    
    sort(candies+1, candies+n+1);
    
    int l = 1, r = n;
    while (l <= r)
    {
   
        if (candies[l] + candies[r] <= w)
        {
   
            l++;
            r--;
        }
        else
        {
   
            r--;
        }
        cnt++;
    }
    
    cout << cnt;
    
    fclose(stdin);
    fclose(stdout);
	return 0;
}

3. LC452 气球射击

3.1 审题

题目描述

游乐园举办了一场射气球的比赛，如果谁能使用最少的弓箭数量引爆所有气球，则会得到"最佳射手奖"。
规则如下：
在二维空间中有 $n$ 个直径不同的球形气球，对于每个气球，提供的是水平方向上气球直径的开始和结束坐标。由于气球是被水平牵引的，所以Y坐标并不重要，因此只要知道气球直径的开始和结束的X坐标就足够了。每个气球的直径的开始坐标一定小于结束坐标。
一支弓箭可以沿着 $X$ 轴从不同点完全垂直地射出。在坐标 $X$ 处射出一支箭，若有一个气球的直径的开始和结束坐标为 $(a, b)$ ，只要满足 $a \leq X \leq b$ ，则该气球会被引爆。
可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。
如果要将所有气球全部被引爆，最少需要多少支弓箭呢？

输入描述

第一行有一个正整数 $n$ ( $1\le n\le1000$ )
接下来有 $n$ 行，每一行有 $2$ 个正整数 $a$ ， $b$ ，分别表示气球直径的开始坐标和结束坐标（ $1\le a,b\le 32767$ ）。

输出描述

单独一行，表示引爆所有气球所需弓箭的最小数量。

样例1

输入
4
10 16
2 8
1 6
7 12
输出
2

3.2 思路

将气球的坐标按照结束点的大小进行排序。

设置射击数量变量 $c n t$ 为 $1$ ，同时设置一个变量 $e n d$ 表示当前射击的结束点。

遍历气球的坐标数组，对于当前的气球坐标 ( $s t a r t, e n d$ )：

如果 $s t a r t > e n d$ ，表示当前气球的起始点在之前的射击结束点之后，说明需要增加一个射击的数量，同时更新 $e n d$ 为当前气球的结束点。

否则，表示当前气球的起始点在之前的射击结束点之前，说明当前气球可以用同一支箭射击，不需要增加射击的数量，但是需要更新 $e n d$ 为当前气球的结束点。

当遍历结束后， $c n t$ 的值即为最少需要的射击数量。

3.3 参考答案

#include <iostream>
#include <algorithm>
using namespace std;

int n, cnt = 1;

struct Node
{
   
    int start, end;
}balloon[1005];

bool cmp(Node a, Node b)
{
   
    return a.end < b.end;
}

int main()
{
   
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
   
        cin >> balloon[i].start >> balloon[i].end;
    }
    
    // 按照结束点排序
    sort(balloon+1, balloon+n+1, cmp);
    
    int end = balloon[1].end;
    for (int i = 2; i <= n; i++)
    {
   
        // 如果当前气球起始点再之前的结束点之后
        if (balloon[i].start > end)
        {
   
            cnt++; // 增加射击数量
            end = balloon[i].end; // 更新射击结束点
        }
    }
    
    cout << cnt;
	return 0;
}