2010-1107

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

*贪心

由于没有要求一定要按照输入顺序solve trap，所以首先要按照deadline的升序排序,从而确定了逃脱的顺序。

建立一个存储cost的大根堆，每次按如下操作贪心。
{{{
将cost[ i ]加入堆，总时间time += cost[ i ]  //首先假设采用耗时方法solve trap
while ( time > deadline[ i ] )           //如果无法耗时方法
     time -= top; pop(); hp--;          //选取之前耗时最大的trap，采用耗血方法solve trap
if ( hp <= 0 ) No Answer..
}}}
因为耗血是逼不得已的时候才能采取的操作，所以为了使每次耗血能让主人公获得更多逃脱的时间，所以就替代之前耗时最大的trap..
{{{
#include<cstdio>
#include<cstdlib>
#include<queue>

using namespace std;

typedef struct {
    int t, d;
} rec;
int n, k, ans, now;
rec trap[ 25000 ];
int cmp( const void *_a, const void *_b )
{
    rec a = *( rec* )_a, b = *( rec* )_b;
    if ( a.d != b.d ) return a.d - b.d;
    else                    return b.t - a.t;
}
int main()
{
    int i;
    while ( scanf( "%d %d", &n, &k ) != EOF  ) {
        priority_queue<int> heap;
        for ( i = 0; i < n; i++ )
            scanf( "%d %d", &trap[ i ].t, &trap[ i ].d );
        qsort( trap, n, sizeof( trap[ 0 ] ), cmp );
        for ( now = ans = i = 0; i < n; i++ ) {
            heap.push( trap[ i ].t );
            now += trap[ i ].t;
            while ( ans < k && now > trap[ i ].d ) {
                ans++;
                now -= heap.top();
                heap.pop();
            }
        }
        if ( ans == k ) printf( "-1\n" );
        else printf( "%d\n", ans );
    }
    return 0;
}
}}}

*贪心

由于没有要求一定要按照输入顺序solve trap，所以首先要按照deadline的升序排序,从而确定了逃脱的顺序。

建立一个存储cost的大根堆，每次按如下操作贪心。

将cost[ i ]加入堆，总时间time += cost[ i ]    //首先假设采用耗时方法solve trap
while ( time > deadline[ i ] )           //如果无法耗时方法
     time -= top; pop(); hp--;          //选取之前耗时最大的trap，采用耗血方法solve trap
if ( hp <= 0 ) No Answer..

因为耗血是逼不得已的时候才能采取的操作，所以为了使每次耗血能让主人公获得更多逃脱的时间，所以就替代之前耗时最大的trap..

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
typedef struct {
    int t, d;
} rec;
int n, k, ans, now;
rec trap[ 25000 ];
int cmp( const void *_a, const void *_b )
{
    rec a = *( rec* )_a, b = *( rec* )_b;
    if ( a.d != b.d ) return a.d - b.d;
    else                    return b.t - a.t;
}
int main()
{
    int i;
    while ( scanf( "%d %d", &n, &k ) != EOF  ) {
        priority_queue<int> heap;
        for ( i = 0; i < n; i++ )
            scanf( "%d %d", &trap[ i ].t, &trap[ i ].d );
        qsort( trap, n, sizeof( trap[ 0 ] ), cmp );
        for ( now = ans = i = 0; i < n; i++ ) {
            heap.push( trap[ i ].t );
            now += trap[ i ].t;
            while ( ans < k && now > trap[ i ].d ) {
                ans++;
                now -= heap.top();
                heap.pop();
            }
        }
        if ( ans == k ) printf( "-1\n" );
        else printf( "%d\n", ans );
    }
    return 0;
}