算法笔记2-(贪心算法)
求解问题时通常采取当前看来最佳的选择策略。此外，在某些情况下这仅是一种特定意义下的局部最优解，并非全局最优解。然而要确定其是否为全局最优则需进行相应的证明
一、硕鼠的交易 HDOJ 1009
结构体数组排序法
二、田忌赛马HDOJ1052
两次贪心，先比较最大，在分析最小，然后去掉比较过的马
1、用田最快的VS齐最快的，赢则比
1.2、输则，用田最慢的VS齐最快的，输
1.3、平则，
1.田最慢的VS齐最慢的，赢则比
2.输或平则，用田最慢的VS齐最快的，输
三、今年暑假不AC HDOJ 2037
事件序列包含的事件数目，称之为该事件序列的长度。
已知事件的起始时间和结束时间，并且在时间轴上无交集的情况下，请确定最长的时间序列以及同时拥有最多数量的事件。
找到最好的贪心思路，贪哪个部分的心
选择在不影响前面已经发生的事件的情况下，选择结束时间最早的活动
四、搬桌子HDOJ 1050
在房间俩侧各有100个房间，中间走廊仅允许搬桌子时一次通过一个
若出现相交错的位置，则经过那个房间的次数++
走廊上下对称，则可看成同一地址
最终，经过某个房间次数最大的数就是需要使用走廊的最多次数
可图形判定
两种概念：
- 度数列：将图G的所有顶点度数排列为一个序列S，则称此序列为图G的度数列
2. 如果一个非负整数组成有限序列满足成为某无向图度序列，则被称为可图；当这样的情况发生时，则称其为可图
Havel-Hakimi定理：(握手定理)
由非负整数构成的递减序列s（称为度序列）：d_{{\rm{}}}¹, d_{{\rm{}}}²,… d_{{\rm{}}}ⁿ（其中n{\geqslant} 2且d_{{\rm{}}}¹\geqslant ¹）是可图的；当且仅当满足以下条件：对于每个i从²到d_{{\rm{}}}¹⁺¹的位置，在s中依次减去一个单位。
满足条件的是一个可图序列。序列s₁包含(n−₁)个非负整数值，在这些度数值中依次减去一之后，则形成一个新序列S₁中的前(d₁)项数值。
1.先对所有数进行递减排序
2.去掉第一个数，其他后面的数每个减一
3.若最后一个结果是零则可图，若出现负数则不可简单图画
例如：3221，去掉首位3其余后三位每个减一，得110
110，去掉首位1其余后面一位减一，得00
0已经是0再减一还是0
321，去掉首位3其余后三位减一，得10
10，去掉首位1其余后一位减一，得-1 出现负数则不可简单图画
——————————————————————————————————————
sort()函数的使用---->排序
- 头文件：使用包含头文件 #include<bits/stdc++.h> 或者采用标准库中的万能头文件
- 排序函数：sort(数据块起始位置, 数据块结束位置后一个位置, [比较函数指针])
- 参数支持：支持传递两个或三个参数
- 参数说明：
- 第一个参数指定要排序数据块的起始位置
- 第二个参数表示数据块结束位置之后的一个位置
- 第三个参数未提供时，默认采用升序排列