学习目标排队打水问题均分纸牌问题删数问题常用操作系统简介(一)常用的操作系统包括Microsoft Windows、Mac OS、UNIX、Linux、Android和iOS。Microsoft Windows:由微软公司开发的图形用户界面操作系统,广泛应用于计算机和智能手机等设备。Windows系统以其易用性和广泛的用户基础著称,支持大量软件应用,但同时也面临较多的安全威胁。Mac OS:由苹果公司开发的操作系统,基于Darwin和Unix内核,具有美观的界面和简洁的操作,但在非苹果PC上无法安装,且软硬件兼容性较差。经典贪心问题· 任务调度问题 之排队打水· 均分纸牌问题· 删数问题贪心没有套路,需要根据不同的题目选择贪心策略,并想办法证明正确性多刷题、多练习是吃透贪心算法的唯一途径排队打水问题有n个人排队到一个水龙头去打水,他们装满水桶的时间为T1,T2,…,Tn为整数且各不相等,找出这n个人排队的一种顺序,使n个人的平均等待时间最小。【输入】第一行为一个整数n。1≤n≤1000第二行n个整数,第i个整数Ti表示第i个人的接水时间Ti。1≤Ti≤10^6【输出】输出有两行,第一行为一种平均时间最短的排队顺序;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。【输入样例】1056 12 1 99 1000 234 33 55 99 812注意· 10个数,对应10个人各自的接满水所需时间→· 每个人按出现顺序编号1~10【输出样例】3 2 7 8 1 4 9 6 10 5//接水顺序:3号第一个接水,2号第二个 …291.90//上面接水顺序下的平均等待时间贪心策略:接水时间短的人应该先打水4个人打水,按升序排好的接水时间分别是T1、T2、T3、T4。我们关心黄色部分的总和:【总等待时间】贪心策略:接水时间短的人应该先打水贪心算法的基本思路:所有人按打满水的时间升序排序(每个人的信息包含:编号id和打水时间T)顺序遍历队列,输出编号,并累计总等待时间sS(n-1)xT1(n-2)xT2 … 1xTn-1 0xTn计算平均等待时间:avgS/n定义结构体person保存个人信息structperson{intid;// 编号intt;// 打满水需要的时间}a[1010];定义比较函数:接水快的排前面boolcmp(person a,person b){if(a.tb.t)returntrue;elsereturnfalse;}调用sort函数进行排序#includesort (a, a n, cmp);所有人按打水的时间升序排序主函数输入n,以及n个人各自打满水需要的时间所有人按打满水的时间升序排序顺序遍历队列,输出编号,并累计总等待时间S输出平均等待时间avgS/nintmain(){intn;cinn;for(inti0;in;i){cina[i].t;a[i].idi1;//编号从1开始}sort(a,an,cmp)longlongs0;//避免数值溢出for(inti0;in;i){couta[i].id ;sa[i].t}coutendl;doubleavg((double)s)/n;//避免整除保留小数或者 avg (1.0*s)/n;printf(%.21f n,avg);return0;}完整代码#includeiostream#includealgorithmusingnamespacestd;constintN1010;structperson{intid;// 编号intt;// 打满水需要的时间}a[1010];//定义比较函数:接水快的排前面boolcmp(person a,person b){if(a.tb.t)returntrue;elsereturnfalse;}intmain(){intn;cinn;//初始化数组for(inti0;in;i){//时间复杂度O(n)cina[i].t;a[i].idi1;//编号从1开始}//所有人按打满水的时间升序排序---时间复杂度O(nlogn)sort(a,an,cmp)longlongs0;//避免数值溢出(初始化总的等待时间)for(inti0;in;i){//时间复杂度O(n)couta[i].id ;//累计总的等待时间sa[i].t}coutendl;//计算平均等待时间doubleavg((double)s)/n;//避免整除保留小数或者 avg (1.0*s)/n;printf(%.21f n,avg);return0;}整体时间复杂度?O(nlogn)均分纸牌有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。【输入格式】N(N堆纸牌,1 N 100)A1 A2…An (N堆纸牌,每堆纸牌初始数,I Ai 10000)【输出格式】所有堆纸牌数量均达到相等时的最少移动次数。贪心算法实现步骤:输入n堆牌的数量到数组a[]求出平均数ave然后从第1堆开始遍历到第n-1堆牌,如果堆中的牌数不等于平均值,就移动牌数与平均值的差值张牌给下一堆牌,并累计移动次数cnt输出cntintmain(){inta[101]{0};intn,sum0;cinn;for(inti1;in;i){cina[i];suma[i];}intavesum/n;//平均数题目确保可以整除intcnt0;for(inti1;in-1;i){if(a[i]!ave){a[i1]a[i]-ave;cnt;}}coutcnt;return0;}完整代码#includeiostreamusingnamespacestd;intmain(){inta[101]{0};intn,sum0;cinn;for(inti1;in;i){cina[i];suma[i];}intavesum/n;//平均数题目确保可以整除intcnt0;for(inti1;in-1;i){if(a[i]!ave){a[i1]a[i]-ave;cnt;}}coutcnt;return0;}(思考】时间复杂度O(n)归纳规律后会发现,最少移动次数可以通过以下公式直接计算:最少的移动次数(N-1)-(前面连续牌数等于均值的堆数)-(最后连续牌数等于均值的堆数)例如,9 8 17 6 的最少移动次数是(4-1)10 9 15 6的最少移动次数是(4-1)-19 15 6 10的最少移动次数是(4-1)-1所以另一种思路是:先统计出“前面连续牌数等于均值的堆数”和“最后连续牌数等于均值的堆数”再用以上公式直接计算#includeiostreamusingnamespacestd;intmain(){inta[101]{0};intn,sum0;cinn;for(inti1;in;i){cina[i];suma[i];}intavesum/n;//平均数intcntn-1;//最少移动次数,初始n-1// 减去 前面连续牌数等于均值的堆数for(inti1;in;i){if(a[i]!ave)break;cnt--;}// 减去 后面续牌数等于均值的堆数for(intin;i1;i--){if(a[i]!ave)break;cnt--;}coutcnt;return0;}【思考】时间复杂度O(n)注意:两种方法的时间复杂度虽然一样,但是由于数据随机,首尾数据刚好等于均值的情况很少,所以这种方法花费的时间相对较短删数问题键盘输入一个高精度的正整数n(n 1000位),去掉其中任意s个数字后剩下的数字按原左右顺序将组成一个新的正整数。编程对给定的n和s寻找一种方案,使得剩下的数字组成的数最小。例如:153748要删除2个数,使得剩下的数字最小,应当删除5和7,得到1348。(注意:1087如果要删除1个数,删除1结果是最小的,得到结果87)【输入】第一行是一个高精度整数n。第二行是需要删除的位数s。【输出】最后剩下的最小数(如果数字最前面有0,0不输出)【输入样例】1537482【输出样例】1348高精度整数在C语言中,任何数据类型都有一定的表示范围。高精度整数,就是非常长的整数,是int和long long都无法存储的整数一般用数组来模拟高精度整数(后面的课程会专门讲高精度运算问题)例如,1000位的高精度数,可以定义一个数组int n[1000]来保存和表示贪心策略:每一步总是删除第一个递减区间的首数字,若只有递增区间,则删除最后一个数字。贪心算法的基本思路:从高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字;否则删除第一个递减区间的首数字,这样删一位便形成了一个新数字串。然后回到最高位,按上述规则再删下一个数字。重复以上过程s次为止,可以得到一个最小的新数字。遍历删数顺序遍历a[],如果前面数比后面的数大,则删掉前面的数,即后面所有字符往前移1。(注意最后一个数要和o比较)重复第4步s次,即删除s个数while(s0){...S--;}while(s--){//删s次// 从头到尾找第一个递 人间的首数字intid;for(id1;idcnt;id)//最后一个元素a[cnt]会和a[cnt1]比较,务必保证a[cnt1]0if(a[id]a[id1])break;//删掉a[id],即后面所有数往前移1for(intjid;jcnt;j)a[j]a[j1];//数的长度减少1个cnt--;}去除前导0顺序遍历数组a,先去除前导0,后输出后面的所有数inti1;// 从头开始查看,直到找到一个非o值或者只剩最后一个值(最后一个即使是0也要留着输出用)while((a[i]0)icnt)i;// 从i开始输出后面的所有元素值while(icnt)couta[i];#includeiostream#includestringusingnamespacestd;constintN1010;string n;//待处理的数ninta[N],cnt,s;intmain(){cinns;for(inti0;in.size();i)a[i1]n[i]-0;cntn.size();//总位数/数的数量if(scnt){cout0;//都被删了,输出0return0;}while(s--){//Asc// 从头到尾找第一个递减区间的首数字intid;for(id1;idcnt;id)if(a[id]a[id1])break;//删掉a[id],即后面所有字符往前移1for(intjid;jcnt;j)a[j]a[j1];//数的长度减少1个cnt--;}//去除前导0//从头开始查看直到找到一个非0值或者只剩最后一个值inti1;while((a[i]0)icnt)i;while(icnt)couta[i];return0;}【思考】时间复杂度最高项是whilefor双层循环O(s*cnt)s:要删除的位数cnt:初始总位数3.本次课程的知识点排队打水问题的贪心算法均分纸牌问题的贪心算法删数问题的贪心算法分发饼干假设你是一位很棒的家长,想要给你的n个孩子们分发m块小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子i,都有一个胃口值gi,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j,都有一个尺寸sj。如果sjgi,我们可以将这个饼干j分配给孩子i,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。【输入】第一行一个正整数n表示孩子数量(n 10),后面一行n个正整数表示每个孩子的胃口值g。第三行一个正整数m表示饼干的数量(m 20),后面一行m个正整数表示每块饼干的尺寸s。【输出】最多能满足多少孩子。【输入样例1】31 2 3211【输出样例1】1【输入样例2】21 232 1 3【输出样例2】2【提示】典型贪心策略,尽可能地用小饼干喂饱胃口小的孩子。首先将两个数组升序排序,再顺序遍历两个数组:1、如果当前饼干喂不饱当前的小孩,那么后面所有的小孩肯定也喂不饱,所以直接查看下一个饼干能否喂饱当前的小孩,直到一个饼干可以喂饱当前的小孩。统计结果加1;2、继续给下一个孩子找饼干。#includeiostream#includealgorithmusingnamespacestd;intg[11];ints[21];intmain(){intn,m;cinn;for(inti0;in;i)cing[i];cinm;for(inti0;im;i)cins[i];// 首先将两个数组从小到大排序sort(g,gn);sort(s,sm);inti0,j0,ans0;//i作为g指针,j为s指针while(injm){if(s[j]g[i]){//满足了一个小孩,g指针后移1,ans加1i;ans;}// 不管当前饼干是否可以满足此小孩,s指针都向后移1j;}coutans;return0;}
C++(贪心算法二)
学习目标排队打水问题均分纸牌问题删数问题常用操作系统简介(一)常用的操作系统包括Microsoft Windows、Mac OS、UNIX、Linux、Android和iOS。Microsoft Windows:由微软公司开发的图形用户界面操作系统,广泛应用于计算机和智能手机等设备。Windows系统以其易用性和广泛的用户基础著称,支持大量软件应用,但同时也面临较多的安全威胁。Mac OS:由苹果公司开发的操作系统,基于Darwin和Unix内核,具有美观的界面和简洁的操作,但在非苹果PC上无法安装,且软硬件兼容性较差。经典贪心问题· 任务调度问题 之排队打水· 均分纸牌问题· 删数问题贪心没有套路,需要根据不同的题目选择贪心策略,并想办法证明正确性多刷题、多练习是吃透贪心算法的唯一途径排队打水问题有n个人排队到一个水龙头去打水,他们装满水桶的时间为T1,T2,…,Tn为整数且各不相等,找出这n个人排队的一种顺序,使n个人的平均等待时间最小。【输入】第一行为一个整数n。1≤n≤1000第二行n个整数,第i个整数Ti表示第i个人的接水时间Ti。1≤Ti≤10^6【输出】输出有两行,第一行为一种平均时间最短的排队顺序;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。【输入样例】1056 12 1 99 1000 234 33 55 99 812注意· 10个数,对应10个人各自的接满水所需时间→· 每个人按出现顺序编号1~10【输出样例】3 2 7 8 1 4 9 6 10 5//接水顺序:3号第一个接水,2号第二个 …291.90//上面接水顺序下的平均等待时间贪心策略:接水时间短的人应该先打水4个人打水,按升序排好的接水时间分别是T1、T2、T3、T4。我们关心黄色部分的总和:【总等待时间】贪心策略:接水时间短的人应该先打水贪心算法的基本思路:所有人按打满水的时间升序排序(每个人的信息包含:编号id和打水时间T)顺序遍历队列,输出编号,并累计总等待时间sS(n-1)xT1(n-2)xT2 … 1xTn-1 0xTn计算平均等待时间:avgS/n定义结构体person保存个人信息structperson{intid;// 编号intt;// 打满水需要的时间}a[1010];定义比较函数:接水快的排前面boolcmp(person a,person b){if(a.tb.t)returntrue;elsereturnfalse;}调用sort函数进行排序#includesort (a, a n, cmp);所有人按打水的时间升序排序主函数输入n,以及n个人各自打满水需要的时间所有人按打满水的时间升序排序顺序遍历队列,输出编号,并累计总等待时间S输出平均等待时间avgS/nintmain(){intn;cinn;for(inti0;in;i){cina[i].t;a[i].idi1;//编号从1开始}sort(a,an,cmp)longlongs0;//避免数值溢出for(inti0;in;i){couta[i].id ;sa[i].t}coutendl;doubleavg((double)s)/n;//避免整除保留小数或者 avg (1.0*s)/n;printf(%.21f n,avg);return0;}完整代码#includeiostream#includealgorithmusingnamespacestd;constintN1010;structperson{intid;// 编号intt;// 打满水需要的时间}a[1010];//定义比较函数:接水快的排前面boolcmp(person a,person b){if(a.tb.t)returntrue;elsereturnfalse;}intmain(){intn;cinn;//初始化数组for(inti0;in;i){//时间复杂度O(n)cina[i].t;a[i].idi1;//编号从1开始}//所有人按打满水的时间升序排序---时间复杂度O(nlogn)sort(a,an,cmp)longlongs0;//避免数值溢出(初始化总的等待时间)for(inti0;in;i){//时间复杂度O(n)couta[i].id ;//累计总的等待时间sa[i].t}coutendl;//计算平均等待时间doubleavg((double)s)/n;//避免整除保留小数或者 avg (1.0*s)/n;printf(%.21f n,avg);return0;}整体时间复杂度?O(nlogn)均分纸牌有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。【输入格式】N(N堆纸牌,1 N 100)A1 A2…An (N堆纸牌,每堆纸牌初始数,I Ai 10000)【输出格式】所有堆纸牌数量均达到相等时的最少移动次数。贪心算法实现步骤:输入n堆牌的数量到数组a[]求出平均数ave然后从第1堆开始遍历到第n-1堆牌,如果堆中的牌数不等于平均值,就移动牌数与平均值的差值张牌给下一堆牌,并累计移动次数cnt输出cntintmain(){inta[101]{0};intn,sum0;cinn;for(inti1;in;i){cina[i];suma[i];}intavesum/n;//平均数题目确保可以整除intcnt0;for(inti1;in-1;i){if(a[i]!ave){a[i1]a[i]-ave;cnt;}}coutcnt;return0;}完整代码#includeiostreamusingnamespacestd;intmain(){inta[101]{0};intn,sum0;cinn;for(inti1;in;i){cina[i];suma[i];}intavesum/n;//平均数题目确保可以整除intcnt0;for(inti1;in-1;i){if(a[i]!ave){a[i1]a[i]-ave;cnt;}}coutcnt;return0;}(思考】时间复杂度O(n)归纳规律后会发现,最少移动次数可以通过以下公式直接计算:最少的移动次数(N-1)-(前面连续牌数等于均值的堆数)-(最后连续牌数等于均值的堆数)例如,9 8 17 6 的最少移动次数是(4-1)10 9 15 6的最少移动次数是(4-1)-19 15 6 10的最少移动次数是(4-1)-1所以另一种思路是:先统计出“前面连续牌数等于均值的堆数”和“最后连续牌数等于均值的堆数”再用以上公式直接计算#includeiostreamusingnamespacestd;intmain(){inta[101]{0};intn,sum0;cinn;for(inti1;in;i){cina[i];suma[i];}intavesum/n;//平均数intcntn-1;//最少移动次数,初始n-1// 减去 前面连续牌数等于均值的堆数for(inti1;in;i){if(a[i]!ave)break;cnt--;}// 减去 后面续牌数等于均值的堆数for(intin;i1;i--){if(a[i]!ave)break;cnt--;}coutcnt;return0;}【思考】时间复杂度O(n)注意:两种方法的时间复杂度虽然一样,但是由于数据随机,首尾数据刚好等于均值的情况很少,所以这种方法花费的时间相对较短删数问题键盘输入一个高精度的正整数n(n 1000位),去掉其中任意s个数字后剩下的数字按原左右顺序将组成一个新的正整数。编程对给定的n和s寻找一种方案,使得剩下的数字组成的数最小。例如:153748要删除2个数,使得剩下的数字最小,应当删除5和7,得到1348。(注意:1087如果要删除1个数,删除1结果是最小的,得到结果87)【输入】第一行是一个高精度整数n。第二行是需要删除的位数s。【输出】最后剩下的最小数(如果数字最前面有0,0不输出)【输入样例】1537482【输出样例】1348高精度整数在C语言中,任何数据类型都有一定的表示范围。高精度整数,就是非常长的整数,是int和long long都无法存储的整数一般用数组来模拟高精度整数(后面的课程会专门讲高精度运算问题)例如,1000位的高精度数,可以定义一个数组int n[1000]来保存和表示贪心策略:每一步总是删除第一个递减区间的首数字,若只有递增区间,则删除最后一个数字。贪心算法的基本思路:从高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字;否则删除第一个递减区间的首数字,这样删一位便形成了一个新数字串。然后回到最高位,按上述规则再删下一个数字。重复以上过程s次为止,可以得到一个最小的新数字。遍历删数顺序遍历a[],如果前面数比后面的数大,则删掉前面的数,即后面所有字符往前移1。(注意最后一个数要和o比较)重复第4步s次,即删除s个数while(s0){...S--;}while(s--){//删s次// 从头到尾找第一个递 人间的首数字intid;for(id1;idcnt;id)//最后一个元素a[cnt]会和a[cnt1]比较,务必保证a[cnt1]0if(a[id]a[id1])break;//删掉a[id],即后面所有数往前移1for(intjid;jcnt;j)a[j]a[j1];//数的长度减少1个cnt--;}去除前导0顺序遍历数组a,先去除前导0,后输出后面的所有数inti1;// 从头开始查看,直到找到一个非o值或者只剩最后一个值(最后一个即使是0也要留着输出用)while((a[i]0)icnt)i;// 从i开始输出后面的所有元素值while(icnt)couta[i];#includeiostream#includestringusingnamespacestd;constintN1010;string n;//待处理的数ninta[N],cnt,s;intmain(){cinns;for(inti0;in.size();i)a[i1]n[i]-0;cntn.size();//总位数/数的数量if(scnt){cout0;//都被删了,输出0return0;}while(s--){//Asc// 从头到尾找第一个递减区间的首数字intid;for(id1;idcnt;id)if(a[id]a[id1])break;//删掉a[id],即后面所有字符往前移1for(intjid;jcnt;j)a[j]a[j1];//数的长度减少1个cnt--;}//去除前导0//从头开始查看直到找到一个非0值或者只剩最后一个值inti1;while((a[i]0)icnt)i;while(icnt)couta[i];return0;}【思考】时间复杂度最高项是whilefor双层循环O(s*cnt)s:要删除的位数cnt:初始总位数3.本次课程的知识点排队打水问题的贪心算法均分纸牌问题的贪心算法删数问题的贪心算法分发饼干假设你是一位很棒的家长,想要给你的n个孩子们分发m块小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子i,都有一个胃口值gi,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j,都有一个尺寸sj。如果sjgi,我们可以将这个饼干j分配给孩子i,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。【输入】第一行一个正整数n表示孩子数量(n 10),后面一行n个正整数表示每个孩子的胃口值g。第三行一个正整数m表示饼干的数量(m 20),后面一行m个正整数表示每块饼干的尺寸s。【输出】最多能满足多少孩子。【输入样例1】31 2 3211【输出样例1】1【输入样例2】21 232 1 3【输出样例2】2【提示】典型贪心策略,尽可能地用小饼干喂饱胃口小的孩子。首先将两个数组升序排序,再顺序遍历两个数组:1、如果当前饼干喂不饱当前的小孩,那么后面所有的小孩肯定也喂不饱,所以直接查看下一个饼干能否喂饱当前的小孩,直到一个饼干可以喂饱当前的小孩。统计结果加1;2、继续给下一个孩子找饼干。#includeiostream#includealgorithmusingnamespacestd;intg[11];ints[21];intmain(){intn,m;cinn;for(inti0;in;i)cing[i];cinm;for(inti0;im;i)cins[i];// 首先将两个数组从小到大排序sort(g,gn);sort(s,sm);inti0,j0,ans0;//i作为g指针,j为s指针while(injm){if(s[j]g[i]){//满足了一个小孩,g指针后移1,ans加1i;ans;}// 不管当前饼干是否可以满足此小孩,s指针都向后移1j;}coutans;return0;}
