题意:
给n把枪,m个怪兽,每把枪可消灭1怪兽,并获得能量=枪的攻击力-怪兽的防御力。求如何射杀能获得最多能量?(不必杀光)
思路:
用最大攻击力的枪杀防御力最小的怪兽明显可获得最大能量。如果每把枪都去射杀刚好1点能量都拿不到的怪物,那简直等于把枪全丢掉。
//#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=+;
int a[N], b[N]; int main()
{
//freopen("input.txt", "r", stdin);
int t, n, m;
cin>>t;
while(t--)
{
scanf("%d%d",&n, &m); for(int i=; i<n; i++) scanf("%d",&a[i]);
for(int i=; i<m; i++) scanf("%d",&b[i]); sort(a, a+n);
sort(b, b+m);
int bb=, aa=n-;
LL ans=;
while(aa>= && bb<m && a[aa]>b[bb])
{
ans+=a[aa]-b[bb];
bb++;
aa--;
}
printf("%lld\n",ans);
} return ;
}
AC代码