课程总结（第三周）

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

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

#include
using namespace std;
int main()                       //效率高的实现方式
{
    string s;
    cin>>s;
    int b=s.length();
    int a=0;b-=1;               //分别指向开头和末尾
    while(a>对胃口，和饼干尺寸都进行排序。以饼干为重点，只有当胃口值小于尺寸时，才发给他饼干（会有一些学生没有饼干，但不重要，能解决题目即可）
 
#include    
using namespace std;
vector a;
vector b;                    //本题复习了下vector的用法
int main()                        
{
    int m,n,x,y;
    cin>>m>>n;
    for(int i=0;i>x;
        a.push_back(x);
    }
    for(int i=0;i>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]>共要运输的汽车除以每次运的，若有余数则进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 
using namespace std;
int a[105];
int main()
{
    int n;cin>>n;int ave;
    for(int i=1;i>a[i];ave+=a[i];
    }
    ave=ave/n;
    for(int i=1;is;
    n=s.length();
    int k=n-m,t=0,c=0,temp;
    while(k--)                       //需要取的个数
    {
        temp=t;                      //标记要取数的下表
        for(int i=t;is[i]) temp=i;
        }
        a[c++]=s[temp];
        t=temp+1;                   //从取数的下一个开始选取
        m++;                       //每次取一个数，区间都要后移一个单位
    } 
    int i=0;
    while(a[i]=='0'&&i>两人先反向行动，当距离为m时，在考虑想左还是右。本题思路很简单，但代码很繁琐，因为要考虑边界问题，和每个城市金币的数量。（我也只是大致理解代码，后面会自己尝试敲出来代码。另外感觉此题更像是动态规划）
 
 
14.二维贪心。两个数组a.b，都为n，要求取（n/2+1）个下标，使得每个数组所取得的元素和两倍大于此数组所有元素之和---->>>1.根据a[n]的大小对下标进行排序。2.根据排出的下标，对数组b[n]每两个进行比较，取较大的那个。3.如果为偶数，所剩最后一个直接选下。（这种选取方法都至少保证了每个数组中选出的一半大于另外一半，更何况又多选了一个）
 
#include 
#include
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>a[i];
    }
    for(int i=0;i>b[i];
    }
    for(int i=0;i