贪心顾名思义，就是选择当前最好的，当然很多时候太贪婪不是一件好事，因为目光短浅，没有考虑到后面的事情，结果没有办法保证最后的结果做到最好。
这就是贪心最难的地方，你可能知道需要使用贪心，但是你无法证明的时候，贪心的局部最优可能最后的WA。
题目0：部分背包问题
题目的含义就是，你可以随便选任意东西，而且可以选0.00001个这种，说明这个背包一定可以装满，所以只需要单位价值最高到低排序即可。
#include<stdio.h>
#include<algorithm>
using namespace std;
struct Node {
int w, v;
}memo[110];
bool cmp(Node a, Node b) { return ((a.v) * (b.w)) > ((a.w)* (b.v)); }
int main() {
int n, m;
scanf("%d%d", &n, &m);
double ans = 0;
for (int i = 0; i < n; i++) scanf("%d%d", &memo[i].w, &memo[i].v);
sort(memo, memo + n, cmp);
for (int i = 0; i < n; i++) {
if (memo[i].w <= m) ans += memo[i].v, m -= memo[i].w;
else {
ans += memo[i].v * m * 1.0 / (memo[i].w * 1.0);
break;
}
}
return 0 * printf("%.2lf", ans);
}题目1：排队接水
人数一定，最后一个人要等待的时间最长且是前n-1个人的时间之和，那么最后一个打水是要最多的；倒数第二也一样，然后后面用数学归纳法接口。因此只需要从小到大排序即可。
#include<stdio.h>
#include<algorithm>
using namespace std;
struct a { int consume, seq; }memo[1010];
bool cmp(a x, a y) { return x.consume < y.consume; }
int main(){
int n, i, j;
double t = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++){
scanf("%d", &memo[i].consume);
memo[i].seq = i;
}
sort(memo + 1, memo + n + 1, cmp);
for (i = 1; i <= n; i++) printf("%d ", memo[i].seq);
printf("\n");
for (j = n - 1; j > 0; j--){
i = n - j;
t += memo[i].consume * j * 1.0;
}
return 0 * printf("%.2lf", t / n);
}题目2：凌乱的yyy / 线段覆盖
和上面一道题类似，但是这道题需要按照结束的时间段排序，然后从前往后选，这样就能够保证参加的比赛最多的情况了。
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct match{
int begin;
int end;
}memo[1000010];
bool book[1000010];
bool cmp(match a, match b){
if (a.end > b.end) return 0;
else return 1;
}
int main(){
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &memo[i].begin, &memo[i].end);
sort(memo + 1, memo + 1 + n, cmp);
for (int i = 1; i <= n; i++){
if (!book[i]){
ans++, book[i] = 1;
for (int j = i + 1; j <= n; j++) if (memo[i].end > memo[j].begin) book[j] = 1;
}
}
return 0 * printf("%d\n", ans);
}题目3：合并果子
就是所谓的结点合并问题，如果你知道哈夫曼树的情况下，这道题就是哈夫曼树；
那么问题来了，如何弄呢？优先队列（或者说用堆）：先输入到堆里面，然后每次选择最小的两个合并然后再将新合并的结点插入到堆中，直到堆只剩下一个元素，那么这个元素就是所得答案。
#include<queue>
#include<iostream>
using namespace std;
priority_queue<int, vector<int>, greater<int> >heap;
int main() {
int n, x, ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> x, heap.push(x);
while (heap.size() >= 2) {
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
ans += a + b;
heap.push(a + b);
}
cout << ans << endl;
return 0;
}题目4：小A的糖果
只需要一边输入一遍处理，然后查看两个数字之和是不是大于x，大于则吃，小于就不吃，记得实时更新。
#include<iostream>
using namespace std;
long long memo[100050];
int main(){
long long ans = 0, n, x;
cin >> n >> x;
cin >> memo[1];
if (memo[1] > x){
ans += memo[1] - x;
memo[1] = x;
}
for (int i = 2; i <= n; i++){
cin >> memo[i];
if (memo[i] + memo[i - 1] > x){
ans += memo[i] + memo[i - 1] - x;
memo[i] = x - memo[i - 1];
}
}
cout << ans << endl;
return 0;
}题目5：删数问题
这道题我们首先要知道，删除的位数是相同，如此，我们删的数在某种意义上肯定越大越好。但是这个大需要怎么考量了？假定243146，删掉6和删掉第一个4相比，肯定是第一个四删了会更小，也就是说我们要删掉第一个碰见的大于两边的数就可以得到最后的答案了。
#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
char s[260];
int main() {
int len, k;
scanf("%s%d", s, &k);
len = strlen(s);
while (k--) {
for (int i = 0; i <= len - 2; i++)
if (s[i] > s[i + 1]) {
for (int j = i; j <= len - 2; j++) s[j] = s[j + 1];
break;
}
len--;
}
int i = 0;
while (i <= len - 1 && s[i] == '0')i++;
if (i == len)printf("0");
else {
for (int j = i; j <= len - 1; j++)
printf("%c", s[j]);
}
return 0;
}题目6：陶陶摘苹果（升级版）
优先摘掉需要力气花的小的就行了（如果搬椅子也要力气那就更难了）。
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct apple {
int h;
int s;
}apple;
apple memo[5050];
bool cmp(apple a, const apple b) { return a.s < b.s; }
int main() {
int n, s, a, b, ans = 0;
scanf("%d%d%d%d", &n, &s, &a, &b);
for (int i = 0; i < n; i++) scanf("%d%d", &memo[i].h, &memo[i].s);
sort(memo, memo + n, cmp);
for (int i = 0; i < n; i++) {
if (memo[i].h <= (a + b) && s >= memo[i].s) ans++, s -= memo[i].s;
}
return 0 * printf("%d", ans);
}题目7：铺设道路
在铺设过程中，我们注意到一旦存在某个地方使得左右存在高度差，那么必然这之间一定会使用高度差的天数的时间来填平；但是一旦平了之后，那么就会一起被带着填平，所以这道题的核心是累计差值。
当然因为是区间操作，因此也可以考虑前缀和和差分的方法来解决这道题。
#pragma warning(disable:4996)
#include<stdio.h>
int memo[100005];
int main(){
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d",&memo[i]);
for (int i = 2; i <= n; i++)
if (memo[i] > memo[i - 1]) ans += memo[i] - memo[i - 1];
return 0 * printf("%d\n", ans + memo[1]);
}题目8：[USACO1.3]混合牛奶 Mixing Milk
优先按照价格从低到高排序，再按照产量排序从高到低即可，当然减的过程中可以一步到位。
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
int price, productive;
}memo[5005];
bool cmp(node a, node b){
if (a.price == b.price) return a.productive > b.productive;
return a.price < b.price;
}
int main(){
int n, m, ans = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
scanf("%d%d", &memo[i].price, &memo[i].productive);
sort(memo, memo + m, cmp);
int i = 0;
while (n){
if (memo[i].productive != 0){
memo[i].productive--;
ans += memo[i].price;
n--;
}
else i++;
}
return 0 * printf("%d\n", ans);
}题目9：纪念品分组
先排序，排序完后两头往中间遍历，然后若和小于给定$\omega$，则直接多一个答案，否则的话就直接使得右边的指针减少（因为当前最小的加这个元素都超过了$\omega$，因此这个可以直接抛掉）。
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
int memo[50000];
int main(){
int w, n, ans = 0;
scanf("%d%d", &w, &n);
for (int i = 0; i < n; i++)scanf("%d", &memo[i]);
sort(memo, memo + n);
int left = 0, right = n - 1;
while (left <= right){
if (memo[left] + memo[right] <= w) left++, right--, ans++;
else right--, ans++;
}
return 0 * printf("%d\n", ans);
}题目10：跳跳！
和上题目类似，只需要从地上跳到最高，然后最高最低最高最低一次跳就OK了
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
long long n, memo[350], ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> memo[i];
sort(memo + 1, memo + n + 1);
int left = 0, right = n;
while (left < right) {
ans += (pow((memo[right] - memo[left]), 2) + pow((memo[left + 1] - memo[right]), 2));
right--, left++;
}
cout << ans << endl;
return 0;
}题目11：分组
这里采用单调栈的方法，首先栈是先进后出的一种数据结构，那么我们在这个时候加上其push到栈里的元素只能为当前栈顶的元素+1，这样一个栈就构成了一个分组；
然后我们需要在特定的时候增加一个新的栈，这个时候就用flag来保证需不需要使用新的栈；
最后我们遍历栈的size取最小值即可。
#include<stdio.h>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn = 100005;
stack<int> st[maxn];
int memo[maxn];
int min(int x, int y) { return x < y ? x : y; }
int main(){
int n, pos = 0, flag = 0, mmin = 1e10 + 5;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &memo[i]);
sort(memo + 1, memo + n + 1);
for (int i = 1; i <= n; i++){
for (int j = pos; j > 0; j--){
if (st[j].top() + 1 == memo[i]){
st[j].push(memo[i]);
flag = 1;
break;
}
else flag = 0;
}
if (flag == 0) st[++pos].push(memo[i]);
}
for (int i = 1; i <= pos; i++){
int temp = st[i].size();
mmin = min(mmin, temp);
}
return 0 * printf("%d\n", mmin);
}题目12：国王游戏
贪心原则是，左手和右手之积越大，则放在最后。
$Proof$:假设队列为${(L_0,R_0),(L_1,R_1)，(L_2,R_2)，…}$其中第0个元素为国王。
先假设只有两个大臣，则奖赏：
$$
Bonus_1=\frac {L_0\times L_1}{R_1}\\
Bonus_2=\frac {L_0\times L_1\times L_2}{R_2}
$$
然后让两个大臣交换位置，则奖赏为：
$$
Bonus_1=\frac {L_0\times L_2}{R_2}\\
Bonus_2=\frac {L_0\times L_1\times L_2}{R_1}
$$
分别记上述两组数据的最大值为
$$
M_1=Bonus_{max}^1和M_2=Bonus_{max}^2
$$
不妨设
$$
M_1<M_2
$$
又因为
$$
\frac {L_0\times L_1}{R_1}<\frac {L_0\times L_1\times L_2}{R_1}
$$
恒成立，故有
$$
\frac {L_0\times L_1\times L_2}{R_2}>\frac {L_0\times L_1}{R_2}
$$
联立上两个不等式有
$$
\frac {L_0\times L_1\times L_2}{R_2}<\frac {L_0\times L_1\times L_2}{R_1}
$$
即
$$
L_1\times R_1<L_2\times R_2
$$
后续的可以使用数学归纳法继续证明；
当然还有一个叫做“洛必达法则”的大佬有更为详细的证明，此处为传送门https://jpp.blog.luogu.org/solution-p1080
然后我们检查数据范围，好家伙还得来个高精度，最后代码如下(有一说一，这题难到我自己都不咋会，强行看题解会的- -)，注意重载完全可以写一个单独的cmp函数，这里借鉴的是dalao的写法。
#pragma warning(disable:4996)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int len_sum = 1, len_max = 1, len_ans = 1;
int sum[10050] = { 0, 1 }, maxn[10050] = { 0, 1 }, ans[10050];
struct tmp{
long long left, right;
bool operator < (const tmp x) const { return left * right < x.left * x.right; }
}coin[1050];
void muti(long long x){
int temp = 0;
for (int i = 1; i <= len_sum; i++) sum[i] *= x;
for (int i = 1; i <= len_sum; i++){
temp += sum[i];
sum[i] = temp % 10;
temp /= 10;
}
while (temp != 0){
len_sum++;
sum[len_sum] = temp % 10;
temp /= 10;
}
}
void cut(long long x){
memset(ans, 0, sizeof(ans));
len_ans = len_sum;
int tmp = 0;
for (int i = len_ans; i >= 1; i--){
tmp *= 10;
tmp += sum[i];
if (tmp >= x){
ans[i] = tmp / x;
tmp %= x;
}
}
while (ans[len_ans] == 0){
if (len_ans == 1)
break;
len_ans--;
}
}
void max(){
if (len_ans > len_max){
for (int i = 1; i <= len_ans; i++)
maxn[i] = ans[i];
len_max = len_ans;
}
else if (len_ans == len_max){
for (int i = len_ans; i >= 1; i--)
if (maxn[i] < ans[i]){
for (int j = 1; j <= len_ans; j++) maxn[j] = ans[j];
len_max = len_ans;
break;
}
}
}
int main(){
int n;
scanf("%d%lld%lld", &n, &coin[0].left, &coin[0].right);
for (int i = 1; i <= n; i++) scanf("%lld%lld", &coin[i].left, &coin[i].right);
sort(coin + 1, coin + n + 1);
for (int i = 1; i <= n; i++){
muti(coin[i - 1].left);
cut(coin[i].right);
max();
}
for (int i = len_max; i >= 1; i--) printf("%d", maxn[i]);
return 0;
}下一个part就是二分啦，二分最重要的是找到数据之间的单调性，具体下一篇再谈嗷。
