翌得：
1.总结接触到的所有贪心题（难易都有）
2.简要了解动态规划

主要是思路。因为每题都各有特点，所以只大致分类。题目包含作业中20余题和上课所讲例题。自己薄弱的题会附上代码。
课上：
1.一个轮船上最多装多少集装箱---->>>重量轻的先装

2.使背包中物品价值最大---->>>根据 （价值/重量） 这个比值，降序排列，塞满背包。由于物品可以分割，最后当所剩重量不足以放下整个物品时，可用性价比乘以所剩重量。
类似问题：
1.老鼠和猫的交易（题F），要求老鼠所得到的粮食最多---->>>根据每个房间所拥有的鼠粮和猫所需要的猫粮比值，降序排列。同样，当老鼠所拥有猫粮不足以换取整个房间时，可根据比例换取。
2.牛吃花的问题，拉牛需要的2t分钟，和牛吃花的速度，求最少吃的花---->>>根据牛吃花的速度和拉牛所需时间排序都是行不通的。由于拉牛的同时其他牛也在吃，且吃的速度不同。可根据 s1/t1 和 s2/t2进行排序，因为要避免小数。所以改除为乘。s1*t2<s2*t1*

3.找零问题，用最少的纸张找出同等金额的钱---->>>每次都选面额较大的纸张,根据所要找零除以当前最大面额的除数，一次次向面额较小的循环即可。
类似问题：
小岛选举（题X）：使得支持的人最少却能通过提案---->>>要求有一半多一个队，且这些队的人数要比一半多一个即可。

4.区间调度问题。两个数组分别表示开始时间和结束时间，使得参与的工作最多—>>>根据结束时间进行排序，下一个工作的开始时间要大于上一个工作的结束时间即可。此题好用的工具 pair<int ,int>itv[n] ,可对数组进行合并处理。（itv[i].first ,itv[n].second）
类似问题：
1.看节目要求看的节目最多（题K）---->>>也是根据结束时间进行排序，早结束的先看。因为这么做同时用控制了节目时间的跨度。
2.雷达问题，要求用最少的雷达数目检测出给出岛屿（题C）---->>>核心的思路是一样的。此题难点在于将岛屿位置转化到雷达的探测范围，再开一个结构体记录两端位置。根据末端进行排序即可。
3.要求一个数集包含每个区间至少2个元素（题T）---->>>根据区间的后坐标进行排序。总数从2计起，分别标记第一个区间靠后的两个整数。然后考虑下一个区间是否有重叠，若没有累加2，更新标记；若有，和标记1作比较，考虑是否要累加1。
4.课上例8。要求一个数集至少包含每个区间至少一个元素---->>>同样按照后坐标排序，处理方法与<3>类似！

5.**根据字典序进行排序。**输入一个字符串，移动头部尾部元素，得到一个最小的字符串---->>>字典序：比较字符串第一个字符，若相等，任取一个，然后移动到下一个。比较原字符串首位末位，取较小的。

#include<bits/stdc++.h>
using namespace std;
int main()                       //效率高的实现方式
{ 
    string s;
    cin>>s;
    int b=s.length();
    int a=0;b-=1;               //分别指向开头和末尾
    while(a<=b)
    { 
        bool f=false;
        for(int i=0;a+i<=b;i++)  //此处i大多是等于0时，便执行完毕。除非两端相等，才会执行进行++操作
        { 
            if(s[a+i]<s[b-i])
            { 
                f=true;
                break;
            }
            else if(s[a+i]>s[b-i])
            { 
                f=false;
                break;
            }
        }                           //i++并不影响a,b的值，只是起到退出循环的作用。两端去谁都行
        if(f) putchar(s[a++]);
            else putchar(s[b--]);
    }
    return 0;

6.分发饼干，胃口值和饼干尺寸的比较，要满足最多的学生---->>>对胃口，和饼干尺寸都进行排序。以饼干为重点，只有当胃口值小于尺寸时，才发给他饼干（会有一些学生没有饼干，但不重要，能解决题目即可）

#include<bits/stdc++.h> 
using namespace std;
vector<int> a;
vector<int> b;                    //本题复习了下vector的用法
int main()                        
{ 
    int m,n,x,y;
    cin>>m>>n;
    for(int i=0;i<m;i++)
    { 
        cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<n;i++)
    { 
        cin>>y;
        b.push_back(y);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int res=0,index=b.size()-1;
    for(int i=a.size()-1;i>=0;)    //胃口作为循环条件
    { 
        if(index>=0)               //标记饼干数量，关键
        { 
            if(a[i]<=b[index])
            { 
                res++;index--;    //只有能满足孩子时，才给予饼干
            }
            i--;
        }
        else break;
    }
    cout<<res<<endl;
    return 0;
}

7.小船过河，两人过同渡，船速为慢的人所需时间，还需一人将船划回---->>>两种贪心方式。一种是利用最快的人所用时间来运输最慢的人；另一种是利用最快的和次快的来交换最慢的和次慢的。
（2*a[0]+a[n-1]+a[n-1]）和(a[0]+2*a[1]+a[n-1]),分别运最慢的两个人，和两个最慢的人一起走。
类似问题：
轮渡运输汽车，所需的最小时间(题W）---->>>共要运输的汽车除以每次运的，若有余数则进1，则是需要的趟数。轮渡回来的时间与下一趟中最后要运的汽车到达时间作比较。

8.在截止日期日前交上作业，要求所被扣的分最少（例题+题J）---->>>将所有作业不交所要扣得分从大到小降序排列，扣分高的便假设正好在截止日期那一天完成。下一份作业根据截止日前向前便利，若碰到一天没有被占，则不必被扣分。
类似问题：
超市产品截止日期前卖出产品，要求最大利益（题B）---->>>将所有产品的利润降序排列，每一个产品都从截止日期向前遍历，占用的天数则标记为1，累加利润。若没有剩下天数被占据，则是亏损的利润。

9.两个物体相撞化为一个，不断重复，最终所得物体最小---->>>不难发现，先参与碰撞的重量被开方的次数多。因此使得重量最大的两个先撞。思路1：可以先进行降序排列，因为前面重量大的碰撞完后肯定大于后面的元素，直接往下撞即可。思路2：利用优先队列priority_queue q每次最大的元素在队首，两次q.pop操作取得两个最大值，碰完后再q.push存入，（n-1）次循环。

10.两件工作超出时间进行补偿，问老板所要付的最少工资---->>>要使得工作时间长的a搭配工作时间短的b，减去额定时间t，才付的最少。
类似题目：
1.满足客户提交酸奶，每周的价格和需求不同，可存储到仓库，问最少成本（题Y）---->>>第一周成本是固定的，第二周酸奶成本和第一周酸奶成本加上仓库费用作比较，取最小值，依次循环，更新最小值。
2.移动砖头使得所有碓数的砖头一样（题Q）---->>>降序排列，求出平均值，再算出高于平均值的砖头数累加即可（不必关注砖头具体放到哪一堆上了）
而课上所讲：分发纸牌，可当做（2）题Q的升级版。
题目要求增加了移动规则，左端纸牌只能右移，右端纸牌只能左移，中间纸牌可以移向两端，问的是最少移动次数---->>>正好为平均值的牌不必移，重点在于跳过这些堆，移动次数才能最小。因为要移动的总牌数是不变的，可以规定方向，每堆牌减去平均牌，两端为0跳过，中间为0跳过。（便决定了不好用for循环，用while更为合适）

#include <bits/stdc++.h>
using namespace std;
int a[105];
int main()
{ 
    int n;cin>>n;int ave;
    for(int i=1;i<=n;i++)
    { 
        cin>>a[i];ave+=a[i];
    }
    ave=ave/n;
    for(int i=1;i<=n;i++)
    { 
        a[i]-=ave;
    }
    int i=1,j=n,s=0;
    while(a[i]==0&&i<j) i++; //清除左端为0
    while(a[j]==0&&j>i) j--; //清除右端为0
    while(i<j)
    { 
        a[i+1]+=a[i];
        s++;
        a[i]=0;
        while(a[i]==0&&i<j) i++; //执行i++，顺便跳过中间为0情况
    }
    cout<<s<<endl;
    return 0;
}

11.一个序列n去除m个数，使得序列值最小---->>>反过来，就是从序列n中取(n-m)个数，使得数最小。在1到（n-m+1）个数中取一个最小.假设在x处取得，那么在[x+1,n-m+2]中第二个数，以此类推。对于此题，思路取一组数其实不难想到，我觉得实现的代码更重要一点

#include<bits/stdc++.h>
using namespace std;
char a[1005];
int main()
{ 
    memset(a,0,sizeof(a));
    int n,m;
    cin>>m;
    string s;
    cin>>s;
    n=s.length();
    int k=n-m,t=0,c=0,temp;
    while(k--)                       //需要取的个数
    { 
        temp=t;                      //标记要取数的下表
        for(int i=t;i<=m;i++)        
        { 
            if(s[temp]>s[i]) temp=i;
        }
        a[c++]=s[temp];
        t=temp+1;                   //从取数的下一个开始选取
        m++;                       //每次取一个数，区间都要后移一个单位
    } 
    int i=0;
    while(a[i]=='0'&&i<k) i++;    //清除取得数前置0
    if(i==k) cout<<"0"<<endl;
    for(;i<c;i++)
    { 
        cout<<a[i];
    }
    return 0;
}

12.田忌赛马类的问题。M个人每人发n张牌，问一个人手上牌数最少赢几轮----->>>用自己手上最大的牌和这一轮能赢的最大牌比较。
思路1：若正好是自己有，则自己赢；不然输，记录会输的几轮，当再次相等时，则用会输的轮递减，减到0，自己才能继续赢。
思路2：最少赢几轮，可转化为最多输几轮。若自己手上的牌只要有比别人小的便输。
类似问题：
满足客户对于不同规格包裹的需求，所要包裹都是从6*6上裁剪出来的，问最少要消耗多少6*6的包裹（题M）----->>>6*6 5*5 4*4都需要一个单独的6*6的包裹，一个6*6的包裹会分成4个3*3的包裹，此时需要对3*3包裹的余数进行考虑，分出来2*2（优先）和1*1的包裹减去客户的需求。

sum+=(a[3]+3)/4;//处理需要进1的情况最好的方式

13.两人在城市p，都是独立行动，但相距不超过m，移动n天，要求取得金币最多---->>>两人先反向行动，当距离为m时，在考虑想左还是右。本题思路很简单，但代码很繁琐，因为要考虑边界问题，和每个城市金币的数量。（我也只是大致理解代码，后面会自己尝试敲出来代码。另外感觉此题更像是动态规划）

14.二维贪心。两个数组a.b，都为n，要求取（n/2+1）个下标，使得每个数组所取得的元素和两倍大于此数组所有元素之和---->>>1.根据a[n]的大小对下标进行排序。2.根据排出的下标，对数组b[n]每两个进行比较，取较大的那个。3.如果为偶数，所剩最后一个直接选下。（这种选取方法都至少保证了每个数组中选出的一半大于另外一半，更何况又多选了一个）

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[10005],b[10005],id[10005];
inline bool cmp(const int &i1,const int &i2)
{ 
    return a[i1]>a[i2];   //根据数组a的大小对于下标进行排序，
}                         //a[n]位置不发生变化
int main()
{ 
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    { 
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    { 
        cin>>b[i];
    }
    for(int i=0;i<n;i++)
    { 
        id[i]=i;
    }
    sort(id,id+n,cmp);
    int m=n/2+1;cout<<id[0]+1<<" "; //对于数组a，b来说选取的一半元素都比另一半大
    for(int i=1;i+1<n;i+=2)
    { 
        if(b[id[i]]>b[id[i+1]])   //b[n]选取的第一个时根据a[n]选的，为a[n]最大值下标
            cout<<id[i]+1<<" ";
        else
            cout<<id[i+1]+1<<" ";
    }
    if(!(n&1)) cout<<id[n-1]+1;   //判断n的奇偶
    return 0;
}

15.本周重点所讲题目：共n个命令，主席团从学生给出的p个命令中挑选k个，a[i]为掉头发数量，b[i]为愤怒值。---->>>两种贪心策略。对于学生：掉头发 优先 议员愤怒值；对于主席：议员愤怒值 优先掉头发。关键在于：如何在主席接受的命令中，愤怒值最小，而掉的头发最多。
1.挑选p-k个学生不选的，因为反正会被主席拒绝（愤怒值小的，掉头发多的，此处掉的头发多少不重要，因为是学生站在主席角度考虑）
2.挑选出k个掉头发多的，愤怒值大的（此时是学生站在x学生角度考虑）
3.还要挑选（p-k）个命令，要保证前面k个不被拒绝，要挑选出愤怒值小的，相同情况掉多发多的用于被主席否决。

贪心题目 先总结到这个里，下面简要了解动态规划（DP）。
1.与贪心不同，动态规划要求整体最优。如果用贪心思路去看待动态问题，只能说得到的结果不是最差一种，但也不可能是最优解。
2.一个问题，动态规划要求分解成诸多子问题，逐层下放。采用“自顶向下的分析，自底向上的计算”。
3.方法：大多采用二维数组，逐层向上分析.

经典例题：
1.数塔问题，一个塔每层都有不同的数，要求走过的路线 数的和最大。

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];

int main()
{ 
    int n;cin>>n;
    for(int i=0;i<n;i++)
    { 
        for(int j=0;j<n-i;j++)
        { 
            cin>>a[i][j];
            if(i>0)
            { 
            a[i][j]=max(a[i][j]+a[i-1][j],a[i][j]+a[i-1][j+1]);
            }
        }
    }
    cout<<a[n-1][0];
    return 0;
}

2.一条胡同等效于[0，10]这个区间，一个人开始在“5”这个位置，每秒只能移动一个单位，共掉n个馅饼，问最多能接到多少馅饼---->>>依旧可转化为数塔问题。从最后一秒往前推到0秒，也就是开始所占位置（自底向上计算），即可得到最多的馅饼数。

#include <bits/stdc++.h>
using namespace std;
int a[100005][15];
int main()
{ 
    int n,x,time;cin>>n;int m=0;
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++)
    { 
        cin>>x>>time;
        a[time][x]++;       //每个位置在那一秒可能不只掉一个馅饼
        m=max(m,time);     //标记共多少秒
    }
    for(int i=m-1;i>=0;i--)
    { 
        for(int j=1;j<=10;j++)
        { 
            int k=max(a[i+1][j-1],a[i+1][j+1]);
            a[i][j]+=max(k,a[i+1][j]);
        }
    }
    cout<<a[0][5]<<endl;
    return 0;
}

没什么感悟。就是感觉学的不好，特别垃圾，挫败感很强，得失心也变得很重。只是，依然还会努力，但不期望什么高度。