算法设计与分析课

贪心算法

第一题

最小延迟调度：

贪心算法的基本思想：贪心算法的基本思想为从整体中找到每个小局部的最优解，并将所有局部最优解合并成整体的最优解。能够使用贪心算法解决的问题必须满足以下两个性质：

1、整体的最优解可以通过局部最优解得出。

2、整体能被分成多个局部，且这些局部可以求出最优解。

对于本题的问题，每个客户有自己的服务时间和希望的完成时间。如果对某客户的服务在他希望的完成时间前结束，那么对于该客户的服务则没有延迟，如果对某客户的服务在他希望的完成时间之后结束，则对该客户的服务有延迟，设对客户i的完成时间为F[i]，则延迟时间为F[i]+T[i]-D[i]。

所有客户是整体，每个客户是局部，对于每个局部求其最小延迟时间，得到的整体延迟时间则是最小的，因此贪心的策略为怎么求最小延迟时间。

思路1：按照Ti（服务时间）从小到大排。

思路2：按照Di-Ti（结束时间减去服务时间）从小到大排。

思路3：按照Di（结束时间）从小到大排。

然后进行思路的排除，对于思路1，如果客户的服务时间很小，但是结束时间较大，说明他不急着完成服务；如果客户的服务时间很大，但是结束时间较小，说明他急于完成服务。如果让不急于完成的客户先进行调度，急于完成的客户后进行调度，则会造成较大延迟，不可取。

对于思路2，如果某客户不急于完成服务，则Di很大，但同时其Ti也很大，那么Di-Ti就会很小，先让其调度则会占用大量的时间，造成其他客户的服务开始时间延后，产生较大延迟，不可取。

对于思路3，解释为（copy的）：

对于上述两条解释，第一条说明当客户的期望结束时间相同的时候，最大延迟与对客户服务的先后顺序无关；第二条说明交换相邻的客户i和j（原来是i先于j调度，且Di>Dj）的服务顺序后，最大延迟只会不变或者减小。

这两条都证明了思路3的正确性，只需按完成时间从小到大安排任务即可（没有空闲时间）。

#include<iostream>
#include<cstring>
#define maxn 1000+5
using namespace std;

//贪心算法
//数组T为对客户的服务时间（时间段），数组D为客户希望的完成时间（时间节点），数组F为事件i开始的时间
//如果在客户希望的完成时间之前则服务没有延迟
//如果在客户希望的完成时间之后完成该服务则产生延迟，延迟时间为该服务结束时间减去客户希望的完成时间
//延迟时间为F[i]+T[i]-D[i]
//每一个客户都有延迟时间，根据贪心的思想，要找所有最大的拖延时间中的最小值，这样就会使得总拖延时间最小。

typedef struct Client
{
    int id;
    int t;
    int d;
    int flag;
}Client;

void minArrange(int n, int F[], Client C[], int S[], int &t);
void sortC(int n, Client C[]);
int main()
{
    int t=0;
    int n;
    cin>>n;
    int F[maxn];
    Client C[maxn];
    memset(F, 0, sizeof(F));
    for(int i=0; i<n; ++i) cin>>C[i].t;
    for(int i=0; i<n; ++i) cin>>C[i].d;
    for(int i=0; i<n; ++i)
    {
        C[i].flag=0;
        C[i].id=i;
    }
    int S[maxn];
    memset(S, 0, sizeof(S));
    sortC(n, C);
    minArrange(n, F, C, S, t);
    for(int i=0; i<n; ++i) cout<<S[i]<<" ";
    cout<<endl<<t;
    return 0;
}

void sortC(int n, Client C[])
{
    for(int i=0; i<n; ++i)
    {
        for(int j=i; j<n-1; ++j)
        {
            if(C[j].d>C[j+1].d)
            {
                Client temp=C[j];
                C[j].t=C[j+1].t;
                C[j].d=C[j+1].d;
                C[j].id=C[j+1].id;
                C[j+1].t=temp.t;
                C[j+1].d=temp.d;
                C[j+1].id=temp.id;
            }
        }
    }
}

void minArrange(int n, int F[], Client C[], int S[], int &t)
{
    int temp=C[0].d, index=0, time=0;
    int j;
    for(j=0; j<n; ++j)
    {
        index=C[j].id;
        S[j]=index+1;
        F[index]=time;
        time+=C[j].t;
        //F[index]是第index个开始时间，与客户C[j].id对应，所以下面两行计算时间应该是F[index]而不用F[j]
        //（这里错了很久没看出来，如果把开始时间F这个数组写到Client类中会更清晰一点）
        if(j==0) t=F[index]+C[j].t-C[j].d;
        else if(t<F[index]+C[j].t-C[j].d) t=F[index]+C[j].t-C[j].d;
    }
}