贪心-PPT课件（精心整理）.ppt

文档介绍：贪心每次选择局部最优策略,不考虑对今后的影响。一般来说,时间复杂读较低,容易实现。但很多贪心法并不能得到最优解。即使可以,也很难证明最优性。?给出 n个区间[li,ri](1<=i<=n) (n<=100000) ?选出最少的区间,使之能覆盖数轴[0,l] 数据范围: n<=100000 ?箱子里有 n个玩具,标为 1~n 号。地板上最多同时放 k的玩具。一开始的时候,所有玩具都在箱子里。?小朋友依次要玩 t个玩具,玩具标号分别为 a1,a2 … at, 一个玩具的标号可能在数列 a中出现多次。?当小朋友要玩玩具 ai时,如果该玩具在地板上,不要处理,否则?如果地板上已经有 k的玩具,你选一个玩具放进箱子里。此时地板上有 k-1 个玩具。?如果地板上的玩具数小于 k,将玩具 ai从箱子里取出来放到地板上。?要让小朋友玩完所有 t个玩具,最少要将玩具从箱子里取出来放到地板上多少次? ?一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离 d1、汽车油箱的容量 c(以升为单位)、每升汽油能行驶的距离 d2、出发点每升汽油价格 p和沿途油站数 n,油站 i离出发点的距离 d[i] 、每升汽油价格 p[i] 。?求最少费用。