Section 1.2 milk2

这道题要计算的是最长的有牛被挤奶的时间和最长的没有牛被挤奶的时间。首先用结构体

存储每头牛的起止时间。然后按照开始时间升序排序。定义一个cur的结构体表示当前工作的

起止时间，t =cur.end - cur.begin;代表的是工作的时间，然后当milk[i].begin > cur.end时，

一段连续的工作时间被终止了，则t=cur.begin-milk[i].end是一段没有工作的时间。

每计算出一段时间就和当前的最大时间比较，然后更新最大时间。

/*
ID:yucept21
LANG:C++
TASK:milk2
*/

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXN 5005

typedef struct Milking
{
    int begin;
    int end;
}T;

T milk[MAXN];

int cmp( const void *_p, const void *_q)
{
    T *p, *q;
    p = ( T *)_p;
    q = ( T *)_q;
    return p->begin - q->begin;
}

int main()
{

    freopen( "milk2.in", "r", stdin);
    freopen( "milk2.out", "w", stdout);

    int N;
    int t, lct = 0, lit = 0;
    T cur;
    scanf( "%d", &N);
    for( int i = 0; i < N; i ++)
        scanf( "%d%d", &milk[i].begin, &milk[i].end);
    qsort( milk, N, sizeof( milk[0]), cmp);
    cur = milk[0];
    for( int i = 1; i < N; i ++) {
        if( milk[i].begin > cur.end) {
            t = milk[i].begin - cur.end; //没有牛被挤奶的时间
            if( t > lit)
                lit = t;

            t = cur.end - cur.begin; //连续工作时间
            if( t > lct)
                lct = t;

            cur = milk[i]; //因为连续时间终止了，所以要重新计算当前工作时间
        }
        else {
            if( milk[i].end > cur.end)
                cur.end = milk[i].end;
        }
    }
    t = cur.end - cur.begin;
    if( t > lct)
        lct = t;

    printf( "%d %d\n", lct, lit);
    return 0;
}

另一种算法，对时间枚举

/*
ID:yucept21
LANG:C++
TASK:milk2
*/

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXN 1000005

int tt[MAXN];

int main()
{

    freopen( "milk2.in", "r", stdin);
    freopen( "milk2.out", "w", stdout);

    int N, s, f, now = 0;
    int lct = 0, lit = 0, ct = 0, it = 0, mf = 0;
    bool isstart = false;
    memset( tt, 0, sizeof tt);
    scanf( "%d", &N);
    for( int i = 0; i < N; i ++)
    {
        scanf( "%d%d", &s, &f);
        tt[s] += 1;
        tt[f] -= 1;
        if( f > mf) mf = f;
    }
    for( int i = 0; i <= mf; i ++)
    {
        if( tt[i] != 0)
            isstart = true;
        now += tt[i];
        if( now == 0)
        {
            if( isstart)
                it ++;
            if( ct > lct)
                lct = ct;
            ct = 0;
        }
        else {
            ct ++;
            if( it > lit)
                lit = it;
            it = 0;
        }
    }
    printf( "%d %d\n", lct, lit);
}

原文链接: https://www.cnblogs.com/Yu2012/archive/2012/01/14/2322398.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/40180

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

Section 1.2 milk2

相关推荐