求求路过的大佬，救救孩子吧
【
链接：https://ac.nowcoder.com/acm/contest/8564/A
来源：牛客网
scimoon 率领的反叛军已经做好了准备
他的手下有 n 个战机，每架战机有一个破坏力 aia_iai
帝国有 m 个基地，每个基地有一个防御值 did_idi，基地有一个价值 viv_ivi
若一个战机的攻击力严格大于基地的防御值，则可以破坏该基地，得到这个基地的价值 v
帝国的后备资源很多，一个基地可以被反复破坏
每架战机最多只能选择一个基地攻击，当然也可以不攻击
求能获得的最大贡献
来源：牛客网
scimoon 率领的反叛军已经做好了准备
他的手下有 n 个战机，每架战机有一个破坏力 aia_iai
帝国有 m 个基地，每个基地有一个防御值 did_idi，基地有一个价值 viv_ivi
若一个战机的攻击力严格大于基地的防御值，则可以破坏该基地，得到这个基地的价值 v
帝国的后备资源很多，一个基地可以被反复破坏
每架战机最多只能选择一个基地攻击，当然也可以不攻击
求能获得的最大贡献
】
这个题我按照下面思路：
>> 将每个基地的价值按照从大到小排序，如果价值相同，则将防御值从小到大排序
>> 然后便利飞机攻击力，如果飞机攻击力>基地防御值d则取该基地的价值v就可以，遍历一遍，得到结果。
>> 为啥只能通过60%啊。。。。。。。
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct
{
int d,v;
} Battle;
bool comp(Battle b1, Battle b2)
{
if(b1.v == b2.v) // 如果价值相同则将防御值从小到大
{
return b1.d < b2.d;
}
return b1.v > b2.v; // 按价值从大到小
}
int main()
{
int n, m;
cin >> n >> m;
Battle *battle = new Battle[m]; //堡垒属性
int *attack = new int[n];
for(int i=0; i < n; i++)
{
cin >> attack[i];
}
for(int i = 0; i < m; i++)
{
cin >> battle[i].d;
}
for(int i = 0; i < m; i++)
{
cin >> battle[i].v;
}
sort(battle, battle+m, comp); // 堡垒排序
long value = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(attack[i] > battle[j].d) // 当i战机的攻击力大于防御值，则将其v加入
{ // 因为价值从大到小的顺序排列
value += battle[j].v;
break;
}
}
}
cout << value << endl;
return 0;
}
全部评论
(0) 回帖