题解 | #Senior's Gun# 机试指南 贪心

Problem Description

Xuejiejie is a beautiful and charming sharpshooter.

She often carries guns, and every gun has an attack power .

One day, Xuejiejie goes outside and comes across monsters, and every monster has a defensive power .

Xuejiejie can use the gun to kill the monster , which satisfies , and then she will get bonus .

Remember that every gun can be used to kill at most one monster, and obviously every monster can be killed at most once. Xuejiejie wants to gain most of the bonus. It's no need for her to kill all monsters.

Input

In the first line there is an integer , indicates the number of test cases.

In each case:

The first line contains two integers , .

The second line contains integers, which means every gun's attack power.

The third line contains integers, which mean every monster's defensive power.

Output

For each test case, output one integer which means the maximum of the bonus Xuejiejie could gain.

薛杰杰这个名字好好听,一听就是拿着枪(扛枪)战斗力爆表的美女 斯哈斯哈


#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=100001;
//自定义降序函数
bool Compare(int x,int y)
{
    return x>y;
}

int main()
{
    int T;
    long long m,n;
    long long a[MAXN],b[MAXN];
    while(scanf("%lld",&T)!=EOF)
    {
        //输入m n
        cin>>m>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
        for(int j=0;j<m;j++)
            cin>>b[j];
        //排序 将a[i]按降序排列 最大值在前
        //将b[j]按升序排列
        sort(a,a+n,Compare);
        sort(b,b+m);
        //此时的a b数组均排序成功
        long long result=0;//总奖金
        for(int i=0;i<n;i++)
        {
            if(a[i]<=b[i] || i>=m)//当此时会退出,第一种情况是 怪兽都被打爆
                //第二种是枪的战斗力不及怪兽的能力,为什么会直接break呢?因为都是按照顺序排序,如果打不过这个怪兽,之后的怪兽会更厉害,会更打不过,于是直接跳出循环
                break;
            result+=a[i]-b[i];
        }

        printf("%lld",result);

    }

    return 0;
}

思路:

需要在a[i]>b[j]的情况下,使a[i]尽可能大,而b[j]尽可能小。贪心策略为用当前剩下的枪去打最弱的怪物,以便让每一枪都能获得当前情况下最大的奖金。

** 数据类型longlong

** 枪的数量,和怪物的数量,不一定是相等的,所以我们这里要特殊处理一下。

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务