基础算法——贪心¶
第一次遇到这个问题是在《挑战程序设计竞赛》的2.2.4节的贪心问题POJ 3069，这个问题适合和之前总结的《区间求并集、交集和差集》两部分结合起来看，因为题目背景较为类似，但是方法却是千差万别，所以尽量不要套模板，多从问题本身入手分析。
参考的资料：
- https://www.cnblogs.com/zeze/p/summer1214.html
- https://blog.csdn.net/a1097304791/category_7989086.html 提供了题目
- 周小博 《浅谈信息学竞赛中的区间问题》
- https://blog.csdn.net/C20191522TL/article/details/78812199
- https://blog.csdn.net/shao824714565/article/details/51878926
- https://blog.csdn.net/a1097304791/article/details/83306758
- https://www.bilibili.com/video/BV1it411a7xo
数字与字符串的转化¶
- LeetCode 12 整数转罗马数字
- LeetCode 13 罗马数字转整数
- LeetCode 273 整数转换英文表示
仅以273为例。给定一个整数，打印该整数的英文描述。
Example 1:
Input: 123
Output: "One Hundred Twenty Three"
Example 2:
Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"
最优装载问题¶
给出n个物体，第i个物体重量为w_i。选择尽量多的物体，使得总重量不超过C。
由于只关心物体的数量，所以装重的没有装轻的划算。只需把所有物体按重量从小到大排序，依次选择每个物体，直到装不下为止。这是一种典型的贪心算法，它只顾眼前，但却能得到最优解。
- 2020 Google Kick Start Round A-Problem 1
找零钱问题¶
给定1、5、10、25、50、100的纸币，每种数量为a_i，想要找出某一金额C，问最少需要的纸币数量（保证能找的开）。
进一步，如果问最多需要多少枚硬币？其实可以进行转化，最多需要的硬币，代表剩余金额最少，于是可以逆向思考，即总金额减去C，凑齐C所需的最少硬币数，这个最少硬币就是剩余的金额。
部分背包问题¶
有n个物体，第i个物体的重量为w_i，价值为v_i在总重量不超过C的情况下让总价值尽量高。每一个物体都可以只取走一部分，价值和重量按比例计算。
- HDU 1009 FatMouse' Trade
- 一本通-1225：金银岛
因为物品可以按比例的取，所以应该每次选取单位价值最大的，那么就应该先按价值排个序
乘船问题¶
有n个人，第i个人的重量为w_i，每艘船的最大载重量为C，且最多只能乘两个人，用最少的船装载所有的人。
- LeetCode 881 救生艇
现根据体重排序，两个指针，一个指向首端，一个指向尾端，依次递减尾端的位置，如果一个重量大的和重量小的能坐在一条船，那么首端的指针前进一个，尾端的指针左移一个；如果不能同时坐下，那么尾端的指针左移，首端的指针不变。
排队问题¶
r个窗口，n个人，每个人都有各自的处理时间，如何让平均等待时间最少。
- 一本通-1319：【例6.1】排队接水
- SJTU OJ 1036. 二哥去取钱（两种排队形式）
后一个人的排队时间等于前一个人的排队时间加上前一个人的处理时间，所以只需要一个变量去记录前一个人的等待时间即可。如果求总和，就另外需要一个变量，每次加上每个人的等待时间。注意第一个人不需要等待，最后一个人的处理时间不能加在等待时间里面。
过河问题¶
这类问题背景有很多变化，比如潜水，过桥，乘船等，模型是有一个工具（可能是灯、船、氧气瓶等）每次最多允许两个人使用，现在要把一群人从一个地方转移到另一个地方，每个人都有一个转移时间，每次转移的消耗时间取决于两个使用的人中最慢的，问如何让总的转移时间最小？
这种题容易掉入一个陷阱，每次用最快的人转移，但是如果去做4060. 最优潜水策略设计，会发现未必每次用最快的人运输所用时间最小，应该是比较最快的两个人运输和用最快的一个人运输的时间来决定采取哪种方案。
- 4060.最优潜水策略设计
-
一本通-1232：Crossing River
-
当n=1时，直接返回
- 当n=2时，时间为两者之间较大者
- 当n=3时，时间为三者之和，无论采用如（4）的哪种策略
- 当n>=4时，假设按时间递增的顺序有ABCD，有两种方案：
(1)采用A来回往返运输CD，则time = C+A+D+A+B
(2)采用AB来回往返运输CD，先AB过去，A返回，CD过去，B返回。则time=B + A+D+B+B
两种方法的大小无法直接判断，所以需要判断：（ C+A+D+A+B）-（B + A+D+B+B）=C+A-2B
均分纸牌¶
- 一本通-1320：【例6.2】均分纸牌(Noip2002)
- 洛谷-P1031 均分纸牌（贪心）
把整个过程想成打欠条和富人发善款就很好理解了。从初始开始，如果多余平均值，就把多出来的部分分给下一个人，如果少于平均值，就向下一个人要过来差值进行补齐，那么到了最后一个人肯定得到的是均值。
田忌赛马问题¶
-
HDU 1052 Tianji -- The horse Racing（基础贪心）
-
若田忌最慢的马可以战胜齐王最慢的马，那么就让它战胜那匹慢马，胜利场次加1。（田忌最慢马 > 齐王最慢马）
- 若田忌最慢的马不能战胜齐王最慢的马，那么它更加不能战胜其他的马，那就让它输，而且输给齐王最快马，失败场次加1。（田忌最慢马 < 齐王最快马）
- 若田忌最慢的马与齐王最慢的马速度相等。此时，不能简单地认为与它打成平手就是最好情况，相反，打平是下下策，为什么呢？
因为自己后面的队友很有可能战胜此时对方的这匹慢马，所以就算自己输一场，队友也能帮忙赢回一场，而胜一场，输一场的收益和打平一场的收益是一样的，而且自己输的时候可以拉对方最快的马下水，给己方最快的马创造更大的胜利机会（因为它失去了一个强劲的对手），也就是说己方最快的马很可能因为自己的牺牲再胜利一场，从这个角度看，还是自己故意输掉比较好。
但是，还有一点需要注意，当自己放水前，如果己方最快的马原本就比对方最快的马快，然后还输给对方最快的马，那么己方最快的马的才华就浪费了，为什么？
很简单，它原本就能赢，需要你放水么？- -！换句话说，这种情况下，自己的牺牲没有一点价值。
所以，在放水时，一定要保证己方最快马不快于对方最快马。满足此条件后，让己方最慢马与对方最快马去比赛（有可能平局），这样，田忌的马就得到了充分的利用。
删数问题¶
输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。输出新的正整数。（n不超过240位）
- 洛谷-P1106 删数问题（一本通-1321：【例6.3】删数问题(Noip1994)）
- 洛谷-P2426 删数
- 洛谷-P1323 删数问题
每一次总是选择一个使剩下的数字最小的删去，那么显然删掉的数字应该在高位，那么就从高位往低位搜索。若数字递增，删掉末尾的数字；否则删掉第一个相邻降序数对的第一个数字。重复s次。注意最后输出结果的时候，要删除前导零。
骑行问题¶
起点与终点相隔4500米。现Charley需要从起点骑车到终点。但是，他有个习惯，沿途需要有人陪伴，即以相同的速度，与另外一个人一起骑。而当他遇到以更快的速度骑车的人时，他会以相应的速度跟上这个更快的人。先给定所有与Charley同路的人各自的速度与出发时间，问Charley以这种方式跟人，骑完4500米需要多少时间。得出的结果若是小数，则向上取整。
输入若干组数据，每组数据第一行n(1≤n≤10000),n为0，表示输入结束，接着输入n行数据，每行2个数据，表示速度v和出发时间t，如果t<0，表示陪伴人提早出发了。
- 一本通-1227：Ride to Office
如果t < 0，那么这个数据是无用的，因为如果后续这个人的速度大于了先出发的这个人的速度，即使后面相遇，速度也不会减慢，如果后续速度小于先出发的人的速度，后续也不会相遇，所以小于0的数据是无效的。
虽然Charley的速度一直在改变，但是与他相遇的没个人的速度是不会改变的，并且每个人都会达到终点，所以在所有到达终点的人里面，时间最少的就是Charley所需要的时间。
平面上的极大点¶
- 一本通-1230：寻找平面上的极大点
在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x≥a,y≥b;
用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。
给定n个点的集合，一定存在若干个点，它们不会被集合中的任何一点所支配，这些点叫做极大值点。
编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。
本题规定：n不超过100，并且不考虑点的坐标为负数的情况
解析：横纵坐标同时考虑较为困难，可以先按照左端点排序，左端点相同则右端点升序。这样后续的点的横坐标就一定大于前面所有点的横坐标，那么只需要考虑纵坐标是否可能包含前面的极大点。比如序对
1,2 1,4 2,2 2,3 3,1
极大点为1,4 2,3 3,1
会发现，每个极大点对都出现在纵坐标出现逆序的时候，也就是从1，4到2，2的时候，2，3到3，1的时候。那么就可以用一个栈来维护前面选出来的点。当出现逆序的时候触发推入条件，推入的时候，如果被推入的点的纵坐标大于栈内的点的纵坐标，意味着可以被覆盖，那么栈顶的点对就被弹出，直到栈顶的纵坐标大于被推入的点的纵坐标。也就是栈维护纵坐标降序。最后把栈内的元素输出即可。
典型题目：¶
- 一本通-1319：【例6.1】排队接水（排队问题）
- SJTU OJ 1036. 二哥去取钱（两种排队形式）
- HDU 1009 FatMouse' Trade（部分背包问题）
- 一本通-1225：金银岛（部分背包问题）
- LeetCode 881 救生艇（乘船问题）
- SJTU OJ 4060.最优潜水策略设计（过河问题）
- 一本通-1320：【例6.2】均分纸牌(Noip2002) 或 洛谷-P1031 均分纸牌（贪心）
- HDU 1052 Tianji -- The horse Racing（基础贪心）
- 洛谷-P1106 删数问题（一本通-1321：【例6.3】删数问题(Noip1994)）
- 洛谷-P2426 删数
- 洛谷-P1323 删数问题
- 一本通-1227：Ride to Office（骑行问题）
- 一本通-1230：寻找平面上的极大点（平面极大点）
- POJ 3045 Cow Acrobats（基础贪心）
- POJ 3253 Fence Repair（基础贪心，优先级队列）
- POJ 3040 Allowance（基础贪心，思维题）
- POJ 3262 Protecting the Flowers（基础贪心，可以证明）
- POJ 1017 Packets（贪心 + 细节模拟，完美正方形，装箱问题）
- POJ 2393 Yogurt Factory（基础贪心）
- AOJ 0033 Ball（DFS + 贪心）
- POJ Best Cow Line（基础贪心）