比较简单的题目,自己的解法实在想不出哪里出错了。。。。
求求路过的大佬,救救孩子吧
【
链接: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; }
#笔试题目#