恶龙与勇者

题目描述:

n条恶龙闯入了王国的领土,为了拯救王国的危机,国王任命你前往冒险者工会雇佣勇者前去讨伐恶龙。每条恶龙的战斗力为ai。每个勇者的战斗力为bi,雇佣他的花费为ci。只有当勇者的战斗力大于等于恶龙的战斗力时,勇者才能击败恶龙。因为勇者都是骄傲的,所以勇者们拒绝互相组队(即每个勇者只能独自一人去讨伐恶龙)。勇者们都具有凝聚空气中魔力的能力,因此可以无限次出战。王国需要金币去灾后重建,需要你计算打败所有恶龙的最小花费。

输入:

第一行输入一个整数T,表示数据的组数。1≤T≤10。 第一行输入n,m,表示龙的数量和冒险者的数量。0<n,m≤10000。 接下来n行,每行一个数字ai表示龙的战斗力。 接下来m行,每行分别为bi和ci,表示冒险者的战斗力和雇佣他的花费。0<=ai,bi,ci≤100000。

输出:

如果能击退恶龙们,请输出最小的花费,如果不能,请输出”Kingdom fall”

样例输入:

2

1 1

6

10 3

3 2

10

14

15

9 10

6 7

样例输出:

3 Kingdom fall

 

先对每个骑士和龙的能力进行sort排序,然后遍历骑士和龙,用最小的代价将龙一条一条击退就好啦~
AC代码:

#include<iostream>
#include<limits.h>
#include<algorithm>
using namespace std;

struct maoxianjia
{
    double att;
    double mesos;
};

int comp(const maoxianjia &a,const maoxianjia &b)
{
    if(a.att == b.att)
    {
        return a.mesos<b.mesos;
    }
    else
        return a.att>b.att;
}

int main()
{
    int t = 0;
    int n = 0;
    int m = 0;
    int sum = 0;
    int mini;
    cin>>t;
    while(t--)
    {
        sum = 0;
        cin>>n>>m;
        int a[n+1];
        for(int i = 0; i < n; i++)
        {
            cin>>a[i];
        }
        maoxianjia b[m+1];
        for(int i = 0; i < m ; i++)
        {
            cin>>b[i].att>>b[i].mesos;
        }
        sort(a,a+n);
        sort(b,b+m,comp);
        if(b[0].att<a[n-1])
        {
            cout<<"Kingdom fall"<<endl;
            continue;
        }
        else
        {
            mini = INT_MAX;
            for(int i = 0; i <n ; i++)
            {
                for(int j = 0; j<m ; j++)
                {
                    if(a[i] > b[j].att)
                    {
                        break;
                    }
                    if(mini > b[j].mesos)
                    {
                        mini = b[j].mesos;
                    }
                }
                sum = sum + mini;
                mini = INT_MAX;
            }
        }
        cout<<sum<<endl;
    }
}

发表回复

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