Tag Archives: 贪心

http://hi.baidu.com/jlw686/blog/item/88cecd08a84ddc900b7b8245.html 1、当河左边的人数>3时，用最小的两个将最大的两个送过岸，此时有两种送法(见程序)，从中选较小的； 2、当河左边的人数==3时，用最小的一个将剩下的两个送过岸； 3、当河左边的人数

每周要提供不同数量单位的酸奶酪，每周生产单位酸奶酪的成本是不同的，你可以选择预先生产然后库存给以后的周，但是有额外的成本，告知一共要提供 N 周酸奶酪，库存每单位酸奶酪每周的代价是 S，告知每周的单位生产成本 C[i] 和 每周需求 Y[i]，问最小代价是多少。 直接贪心。

有 n 个工作要完成，每个工作有时限，每天最多可以进行 m 个任务，每个任务还可以带来不同的收益，问如何安排每天的工作使得收益最大。 用贪心法。 首先对完成时间排序，在给定时间内选择可以获得最大收益的用户。

装机问题，你要装一台电脑，电脑由多个配件组成，给定配件类型 type，名字 name，价格 price，质量等级 quality。在保证预算不超过的前提下求使得电脑质量等级尽可能高的方案。一个电脑的质量等级由质量最低的那个配件等级所决定。 将配件按类型排序，然后二分配件等级，同一个类型的选择价格较低的，由此计算总价格。

将 B 按照升序排列，枚举 B。

有一条通道，通道两侧是房间，现在由于装修问题，要把一些房间里的桌子移到别的房间，但通道很狭窄，每次只能被一次移动所占据，每次移动要10分钟，求移动完这些桌子需要的最少时间？ 基本思路：贪心 （1）首先对输入的若干任务进行排序，按起点node[i].s 从小到大排序。（注意输入的任务有从a 房间到b房间，当a > b时, a,b进行交换） （2）依次枚举某个未被完成的任务，再统计可以同时被进行的任务。这样算做一次。

一组数，要求从中选出一组连续数，满足奇数步的时候加上这个数，偶数步的时候减去这个数，求走完后和最大。 贪心。 顺序加上局部最大的那个数（类似波峰），再减去局部最小那个数（类似波谷），继续加上后来的局部最大数，再减去后面的局部最小，依此类推。 http://blog.csdn.net/xiaofengsheng/archive/2009/03/16/3992924.aspx http://blog.163.com/soonhuisky@126/blog/static/157591739201034090508/

贪心或者搜索，所谓的 havel 定理，直接硬搞。 对度数进行排序，由大到小，对度数最大的节点依次和几个次大的节点相连，然后二者的度数各减 1，直到耗光这个度数最大的节点，然后对剩余的节点再排序，再找出度数最大的节点，再和几个次大的节点相连，然后二者的度数各减 1，直到耗光这个度数最大的节点，如此往返，直到某一点度为负或某一点度大于剩余节点数，就结束。 参考： http://blog.sina.com.cn/s/blog_5c95cb070100d3jr.html

题意:输入 n 个区间和 t，接着输入 n 个区间 seg[i]==>[l, r], 要求找出最少的区间数覆盖区间目标区间[1, t]; 输入样例: 3 10 //n t 1 7 //区间1 ==> [1, 7] 3 6 //区间2 ==> [3, 6] 6 10 //区间3 ==> [6, 10] 输出答案是 2。 强烈推荐这种题目。 直接贪婪法。

题意：有 n 个数的序列中，假设为 seq[i](0 < i < n)挑出 k 个数，使得这 k 个数的乘积最大。 思路：分类讨论。 （１）将数从大到小排序。 （２）当所有元素都小于等于 0,分成两种情况：当 k 为奇数时，输出前 k 个元素，否则输出后 k 个元素 （３）当所有元素都大于等于 0 时，输出前k个元素。 （４）当元素有正有负时，当 k 个奇数时，取出 seq[0]，则剩下 k - 1（偶数个）个元素未选。每次取前两个元素乘积和最后两个元素的乘积进行比较，取乘积较大的两个元素。直到选出 k 个元素。 参考： http://blog.csdn.net/lyg_wangyushi/archive/2009/07/24/4375183.aspx