程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4415 Assassin's Creed（貪心）

HDU 4415 Assassin's Creed（貪心）

編輯：關於C++

HDU 4415

題意：

壯哉我Assassin！
E叔有一柄耐久度為m的袖劍，以及n個目標士兵要去解決。
每解決掉一個士兵，消耗袖劍Ai的耐久度，且獲得該士兵的武器，可以使用該武器解決Bi名其他士兵。
E叔要盡可能地消耗更少耐久度解決更多的敵人，求最小消耗與最大殺敵數。

思路：

我們把士兵分為兩個集合：e1與e2，e1的士兵 Bi = 0 ， e2 的 Bi > 0.

我們發現，如果能解決e2的任意一個，e2即可全滅，那麼我們對e2根據消耗進行升序排序，消滅e2集合的消耗即為排序後的第一個士兵的Ai；

其次，要盡可能多地解決e1的士兵，則同樣對e1根據消耗進行升序排序，殺到耐久度小於下一士兵Ai為止；

乍一看，最優解就是先全滅e2再用剩下的耐久度消滅e1較小Ai的敵人，用e2剩下的Bi消耗e1較大Ai的敵人；
如果不能全滅e2，則用所有耐久度去解決e1的敵人。

這樣做的確很優了，但還不是最優，考慮這組樣例：
1
4 5
2 1
3 1
5 0
100 0
按照剛才的貪心策略，先解決Bi > 0 的前兩個士兵（用袖劍殺死士兵1，用士兵1的武器殺死士兵2），消耗2耐久度，然後用士兵2的武器解決Ai最大的士兵4，士兵3由於耐久度不夠則無法解決，答案是3 2。
但是我們可以先用袖劍殺死士兵1與士兵2，用這兩個士兵的武器去解決士兵3,4，明顯最優解為4 5。

於是我們對之前貪心策略做出改進：
設用袖劍殺死一個 Bi = 0 的士兵1消耗為a，設用士兵武器殺死一個在 Bi > 0 的集合裡的士兵2，士兵2的最小消耗為b；
如果a < b，則用袖劍解決士兵1，用士兵武器解決士兵2；
否則，則用袖劍解決士兵2，保留士兵武器解決更大消耗的士兵（可能是士兵1）；
換而言之，就是E叔面對一個 Bi > 0 的士兵，他說：本來准備用士兵武器殺死你，現在我又不想了，我要用袖劍殺死你，因為你的消耗並不大，我要換回用以殺死你的士兵武器，去殺死消耗更大的敵人。

可能敘述還是有點不清。。這個貪心策略看起來極其像dp，然而它真心不是dp。。以後思路更清晰的時候再改改吧~

代碼：

/*
* @author FreeWifi_novicer
* language : C++/C
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))
#define cls( x ) memset(x,0,sizeof(x))
#define mp make_pair
#define pb push_back
typedef long long lint;
typedef long long ll;
typedef long long LL;

/*Nothing is true , everything is permitted*/

const int maxn = 1e5 + 100 ;
lint n , m ;
lint kill_e1 , cost1 ;
lint ans_cost , ans_kill ;
lint e1[maxn] ;

struct em{
    lint cos , kil ;
}e2[maxn] ;

bool cmp( em a , em b ){
    return a.cos < b.cos ;
}

void only_kill_e1( int len1 ){
    lint dur = m ;
    cost1 = 0 ;
    kill_e1 = 0 ;
    int k = 0 ;
    while( k < len1 && dur >= e1[k] ){
        cost1 += e1[k] ;
        kill_e1 ++ ;
        dur -= e1[k++] ;
    }
}

bool kill_all_e2( int len2 , int len1 ){
    if( !len2 )
        return false ;
    lint dur = m ;
    if( e2[0].cos > dur )
        return false ;
    dur -= e2[0].cos ;
    lint sumb = 0 ;
    for( int i = 0 ; i < len2 ; i++ )
        sumb += e2[i].kil ;
    lint rest = sumb - len2 + 1 ;
    if( rest >= len1 ){//如果多余的sword能夠解決掉所有b = 0的敵人，則可解決所有敵人
        ans_cost = e2[0].cos ;
        ans_kill = n ;
        return true ;
    }
    else{
        int i = 0 , j = 1 ; //比較e2[j].cos 與 e1[i]的大小,選擇消耗耐久度小的去殺
        lint tmp = len1 - rest ;
        ans_cost = e2[0].cos ;
        ans_kill = len2 + rest ;
        while( i < tmp ){
            if( dur < e1[i] && dur < e2[j].cos ) break ;
            if( j < len2 && e2[j].cos <= e1[i] ){
                ans_cost += e2[j].cos ;
                dur -= e2[j].cos ;
                tmp-- ; j++ ;
            }
            else{
                ans_cost += e1[i] ;
                dur -= e1[i] ;
                i++ ;
            }
            ans_kill ++ ;
        }
        return true ;
    }
}
int main(){
//  freopen(input.txt,r,stdin);
    int t ; cin >> t ; int kase = 1 ;
    while( t-- ){
        cin >> n >> m ;
        ans_kill = kill_e1 = 0 ;
        ans_cost = cost1 = 0 ;
        lint len1 = 0 , len2 = 0 ;
        for( int i = 1 ; i <= n ; i++ ){
            lint a , b ;
            scanf( %I64d%I64d , &a , &b ) ;
            if( !b ){
                e1[len1++] = a ;
            }
            else{
                e2[len2].cos = a ;
                e2[len2++].kil = b ;
            }
        }
        printf( Case %d:  , kase++ ) ;
        sort( e1 , e1 + len1 ) ;
        sort( e2 , e2 + len2 , cmp ) ;

        only_kill_e1( len1 ) ;

        if( !kill_all_e2( len2 , len1 ) ){
            printf( %I64d %I64d
 , kill_e1 , cost1 ) ;
            continue ;
        }
        if( ans_kill > kill_e1 ){
            printf( %I64d %I64d
 , ans_kill , ans_cost ) ;
        }
        else{
            if( ans_kill == kill_e1 )
                printf( %I64d %I64d
 , ans_kill , min( ans_cost , cost1 ) ) ;
            else
                printf( %I64d %I64d
 , kill_e1 , cost1 ) ;
        }  
    }
    return 0;
}