信息学奥赛第九节 —— 贪心算法(需要安排几位师傅加工零件 + 排队打水问题)

本文主要是介绍信息学奥赛第九节 —— 贪心算法(需要安排几位师傅加工零件 + 排队打水问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

贪心算法的特点

对于问题求解时,总是做出在当前来看是最好的选择的策略,即贪心算法不从整体来考虑问题。贪心算法与排序、高精度、背包等算法不同,没有一个特定的模板来表达贪心算法的过程。

贪心的步骤
  • 抽象出题目的数学模型
  • 把需要解决的问题分解为许多个小问题
  • 选择一个策略,这个策略对于解决所有的小问题一定是通用的
  • 证明所选择的策略一定适用于所有的情况
  • 把子问题的解合并,就得到了全局的最优解
贪心的证明
  • 反证法
  • 数学归纳法
  • 决策的包容性
  • 范围的缩放
  • 邻项交换法
贪心的入门模型

在这里插入图片描述
如图所示,在上图中,最外面的方框是一个大集合,其中包含了许多个小集合。每个小集合里面又包含了许多个数字。现要在每个集合中选一个数,使得这些数的和最大。应该如何解决?如果使用贪心算法,那么一定选择每个集合中最大的那个数,再将这些数相加,最后得到的一定是最大的结果。
反证法证明策略的正确性:假设从集合1、2、3、4、5中选择最大的数,但是在对集合6进行操作时,只选择集合6中第二大(或者第三大)的那个数,此时所有被选择的数之和为sum1,那么集合6中一定存在一个数,使得选择它之后,所有数的和更新为sum2sum2 > sum1。 从而证明策略的正确性。

贪心例题1 原题链接

题目描述

某工厂有n个零件加工的师傅,每位师傅每天能够加工出不同数量的零件。现有m个零件要求一天加工完,请问该工厂最少需要派几个师傅来完成这次零件加工任务,如果安排所有的师傅都参与加工也不能在一天内完成任务,请输出“NO”

输入

第一行有两个整数,用空格隔开;第一个整数代表要加工的总零件个数m(m<=10 ^ 6),第二个整数代表工厂的零件加工师傅的数量n(n<=100)。第二行有n个整数,分别代表每个师傅每天能够加工出来的零件数量(每个师傅每天加工的零件数量<=10 ^ 4)

输出

工厂在1天时间内加工所有零件需要的师傅数量或者输出NO

样例输入

10 5
1 3 2 4 2

样例输出

4

解题思路:本题是经典的贪心模型。我们要求最少的加工师傅的人数,由于零件总数是固定的,每个师傅每天加工的零件个数也是固定的,故需要采取先让加工零件多的师傅来加工的策略。将每个师傅每天可以加工的零件数量按照从大到小排序,再依次相加。在相加的时候需要标记当前使用了几个师傅,如果加工的零件数量之和大于m,则输出第几个师傅即可。如果直到最后都未能成功加工完m个零件,那么输出"NO"。
AC代码

#include <algorithm>
#include <iostream>
#include <cstring>using namespace std;
const int N = 110;
int a[N];//a[i]:第i个师傅每天可以加工的零件数量//将每个师傅每天可以加工的零件数量按照从大到小排序
bool cmp(int a,int b) { return a >= b; }int main()
{int m,n; cin >> m >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a + 1,a + n + 1,cmp);int sum = 0,flag = -1;//flag用来标记当前使用了几个师傅for (flag = 1;flag <= n;flag++){sum += a[flag];if (sum >= m){cout << flag << endl;return 0;}}//所有师傅每天加工的零件数之和小于mint cnt = 0;for (int i = 1;i <= n;i++) cnt += a[i];if (cnt < m) cout << "NO" << endl;return 0;
}
贪心例题2 原题链接

题目描述

有n个人排队到r个水龙头去打水,他们装满水桶的时间t1,t2,…,tn为整数且各不相等,应如何安排他们的打水顺序才能使他们花费的总时间最少?每个人打水的时间 = 排队的时间 + 实际打水的时间,本题假设一个人打好水,排在他后面的人接着打水的这个切换过程不消耗时间。比如,有2个人A和B,他们打水的时间分别是3和2,只有1个水龙头,这时,如果A先打水,B后打水,那么A和B打水的时间分别为3、3+2(B排队3分钟)。因此,所有人打水的总时间就是每个人的打水时间及每个人的排队时间的总和。

输入

第1行,两个整数n(1<=n<=500)和r(1<=r<=100)。
第2行,n个正整数t1,t2,…,tn,(1<=ti<=1000)表示每个人装满水桶的时间。

输出

1行,一个正整数,表示他们花费的最少总时间。

样例输入

4 2
2 6 4 5

样例输出

23

解题思路:AC本题的要点在于选取正确的贪心策略。

  • 贪心策略1:时间较短的人去水龙头1排队(需要2+6+5+11=24分钟)
    在这里插入图片描述
  • 贪心策略2:打水时间较长的人先打水(需要5+7+6+10=28分钟)
    在这里插入图片描述
  • 贪心策略3:打水时间较短的人先打水(需要2+7+4+10=23分钟)
    在这里插入图片描述

通过分析可以得到第三种策略为正确的贪心策略。即打水快的人先打,总的打水时间才可能比较短。如果打水慢的人先去打水,那么对于在其后排队的人,需要等待的时间会变长。
如果水龙头的个数很多,该如何解决问题?
假设现在有六个水龙头,即r = 6。不难发现,前r个人是不需要排队的,从第r + 1个人开始需要排队等待。
在这里插入图片描述
i个人的接水时间 = 第i个人自己的接水时间 + 前一个人的接水时间(等待时间)。通过上图,可以得到

a[7] = a[7] + a[1];
a[8] = a[8] + a[2];
a[9] = a[9] + a[3];
a[10] = a[10] + a[4];
a[11] = a[11] + a[5];
a[12] = a[12] + a[6];

总结出规律:a[i] = a[i] + a[i - r]
AC代码:

#include <algorithm>
#include <iostream>
#include <cstring>using namespace std;
const int N = 1010;
int a[N];//a[i]:第i个人打水需要的时间int main()
{int n,r; cin >> n >> r;//r表示水龙头的个数for (int i = 1;i <= n;i++) cin >> a[i];//输入每个人的打水时间sort(a + 1,a + 1 + n);//从小到大排序//前r个人不需要排队,可以每人使用一个水龙头for (int i = r + 1;i <= n;i++) a[i] += a[i - r];int sum = 0;for (int i = 1;i <= n;i++) sum += a[i];cout << sum << endl;return 0;
}

当然,可以修剪一下代码,修建之后AC代码如下:

#include <algorithm>
#include <iostream>
#include <cstring>using namespace std;
const int N = 1010;
int a[N];//a[i]:第i个人打水需要的时间int main()
{int n,r;  cin >> n >> r;//r表示水龙头的个数for (int i = 1;i <= n;i++) cin >> a[i];//输入每个人的打水时间sort(a + 1,a + 1 + n);//从小到大排序int sum = 0;for (int i = 1;i <= n;i++) {if (i >= r + 1) a[i] += a[i - r];//前r个人不需要排队,可以每人使用一个水龙头sum += a[i];}cout << sum << endl;return 0;
}

这篇关于信息学奥赛第九节 —— 贪心算法(需要安排几位师傅加工零件 + 排队打水问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/591551

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监