程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5281 Senior's Gun 殺怪

HDU 5281 Senior's Gun 殺怪

編輯：關於C++

題意：給出n把槍和m個怪。每把槍有一個攻擊力，每個怪有一個防御力。如果某把槍的攻擊力不小於某個怪的防御力則能將怪秒殺，否則無法殺死。一把槍最多只能殺一個怪，不能用多把槍殺同一個怪。每殺一次怪可以得到槍的攻擊力減去怪的防御力的的分數。求得分的最大值。

貪心。首先我們考慮這樣一種情況：用攻擊力為A的槍殺防御力為a的怪，攻擊力為B的槍殺防御力為b的怪。則得分為A - a + B - b。

不妨設A ≤ B，則有a ≤ A ≤ B，b ≤ B。如果有A < b，那麼我們考慮用B殺a，而不使用A槍也不殺b怪，那麼得到的分為B - a，和原來的得分相比，多了b分，少了A分，因為A比b小，所以這樣的殺怪方式顯然得分更大。也就是說，對於某兩把槍殺了某兩個怪，如果攻擊力較低的那把槍殺不了比防御力較高的那個怪，那麼就寧願用攻擊力較高的槍去殺防御力較低的怪，不使用攻擊力較低的槍也不殺防御力較高的怪。如此看來，對於一種可行的殺怪方案，要想得分最大，那麼必須有任意一把使用了的槍的攻擊力的不小於任意一個被殺死的怪的防御力。也就是選出來的所有槍和所有怪，隨便用哪把槍殺哪個怪是一樣的。既然這樣，可以先對槍和怪分別按攻擊力遞增和防御力遞增排序，再用攻擊力值最大的槍殺防御力值最小的怪，攻擊力值第二大的槍殺防御力值第二大的怪，以此類推，直到殺不了怪為止，求得的得分即為最大值。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
using namespace std;

const int MAX = 100005;

int n, m;
__int64 a[MAX], b[MAX];

void input()
{
    scanf(%d%d, &n, &m);
    for(int i = 0; i < n; i++)
        scanf(%I64d, &a[i]);
    for(int i = 0; i < m; i++)
        scanf(%I64d, &b[i]);
}

void solve()
{
    sort(a, a + n);
    sort(b, b + m);
    __int64 ans = 0;
    int i = n - 1, j = 0;
    while(i >= 0 && j < m && a[i] > b[j])
        ans += a[i--] - b[j++];
    printf(%I64d
, ans);
}

int main()
{
    int T;
    scanf(%d, &T);
    while(T--)
    {
        input();
        solve();
    }
    return 0;
}