[POJ][3927][贪心] Priest John’s Busiest Day

题目大意

小镇有n场婚礼在一天之内矩形，第i场婚礼的开始时间为Si，结束时间为Ti。在每一场婚礼中，有一个重要仪式，即牧师给予两位新人传达主的祝福。对于第i场婚礼，祝福仪式可以在[Si,Ti]中任何时候举行，但是必须超过总时间的一半以上。

小镇只有一位牧师，所有的祝福仪式都必须要他在场。同时，牧师必须在整数时刻开始或者结束祝福仪式，不过他可以在结束一场之后立刻开始另一场。

现在给你所有婚礼的信息，请问是否能够安排好一个祝福仪式的顺序，使得牧师能够给所有新人带去祝福。

思路

刚开始思路就错了，以为按照每场婚礼的开始时刻排序再模拟就行，后来想想完全不对，根本不是那么一回事。例如(1,1000)和(2,500)这两场婚礼，按照开始时刻贪心，那么结果无疑是NO。

正确的方式应该是按婚礼的祝福仪式的“最早的结束时刻t1”或“最晚开始时间t2”排序再模拟。为何如此？因不管从什么时候开始一个祝福仪式，祝福仪式总是包含时间段(t1,t2)，我们称(t1,t2)为公共时间段，一场婚礼对应一个公共时间段。若存在一个方案可使所有祝福仪式正常举行，那么所有公共时间段也一定都不会出现重合。也由此可得结论，祝福仪式的举行顺序一定与公共时间段的出现顺序相同。

当然，我们不必将公共时间段的开始和结束时刻都求出来，我们只需求出其中一个即可，再依此对婚礼进行排序，最后按顺序模拟婚礼祝福仪式的举行。若所有祝福仪式都能在时间范围内结束，则说明存在一个方案可使所有祝福仪式按时完成，反之不存在。

代码

#include
#include
using namespace std;
struct point
//将每场婚礼的信息封装在结构体中。 
{
    int start;
    int end;
    int mid;
    //mid表示此婚礼的祝福仪式至少持续mid分钟。 
}t[100000];
int n;
int cmp(const void* m,const void* n)
//给婚礼按祝福仪式最早的结束时刻排序。 
{
    return (*(point*)m).start+(*(point*)m).mid-(*(point*)n).start-(*(point*)n).mid;
    //start+mid表示婚礼最早的结束时刻。 
}
bool solved()
{
    qsort(t,n,sizeof(t[0]),cmp);
    long long now=0;
    for(int i=0;it[i].start?now+t[i].mid:t[i].start+t[i].mid;
        //now为当前祝福仪式的结束时间。 
        if(now>t[i].end)
        //如果祝福仪式结束时间晚于婚礼结束时间。 
            return false;
    }
    return true;
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        for(int i=0;i

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注