题目

前言: 没有传送门, 由于出题人的题解有问题, 所以当时的题的数据也可能有问题, 也就是说他们可能还欠我一个气球 -_-

描述

“啊…苍穹幕落…怎么又不能用啊…” 正正最近沉迷于毒(D)奶(N)粉(F)不能自拔, 每天熬夜刷装备已经让正正有了双大大的黑眼圈, 但是正正是一个菜鸡, 他甚至搞不清自己的战斗力是怎么计算的, 为了清楚的知道自己的战斗力, 他特地的请教大佬得知: 每件装备战斗力$=$(1+白字属性值)*(1+黄字属性值)*装备基础分 总战斗力$=$ $\sum$每件装备战斗力 现在有$n$件装备, 但是只能从其中选$m$件, 在你选择的$m$件装备中, 白字属性值每件装备都可以生效, 黄字属性值只有一件装备可以生效, 现在让你帮帮正正, 怎么样选才能让正正战斗力最高

输入

第一行有两个数$n$, $m$($1\le m\le n\le 10000$)表示装备的总数和正正可以选择的装备数. 之后每行有3个数, $v$, $p$, $q$($0\le v\le 10000,0\le p,q\le 5$)分别表示每件装备的基础分, 白字属性值, 黄字属性值

输出

一个数表示最终的战斗力, 答案保留2位小数

样例输入

5 2 100 0.3 0.1 80 0.5 0.2 200 0.2 0.4 100 0.4 0.3 50 0.3 0.6

样例输出

476.00

解决

分析

仔细查看公式与题目描述, 白字属性值是每件装备都可以生效的, 所以在每件装备的战斗力中可以直接使用 (1+白字)*装备基础分, 而对于唯一一件生效的黄字, 可以写成 (1+白字)*装备基础分 + (1+白字)*黄字*装备基础分 , 当所有的装备加起来的时候, 也就是看哪一件装备的黄字生效时附加战斗力最高, 即 (1+白字)*黄字*装备基础分 这一部分最大

设计

创建一个结构体, 两个属性, 基础战斗力 (1+白字)*装备基础分, 加成比率 黄字, 然后按照基础战斗力从大到小进行排序, 由于加成值最大的装备, 可能初始基础战斗力低, 还不如选择一个高基础战斗力的装备, 之后随便一件装备加成一下都比选择加成值最大的战斗力强. 所以分成两种情况, 第一种情况, 基础战斗力优先, 从排序后的装备里, 取出前m个装备, 在他们中找出加成最大的, 使它的黄字生效, 得到一个战斗力; 第二种情况, 加成值优先, 从排序后的装备里, 取出前m-1个装备, 他们的基础战斗力是最高的, 然后在剩余的所有的装备中计算加成值和基础战斗力组合最高的, 将那个装备的黄字生效并且将其战斗力加上去.(如果是在所有装备中计算加成值最高的, 如果在前m-1个里面, 那么为了最大提升战斗力, 必然选择第m件装备, 就与第一种情况相同了), 然后输出两个中最大的战斗力即可

编码

#include <bits/stdc++.h> using namespace std; #define MAX 10005 struct Zhuang_bei { float ji_chu_zhan_dou_li; float jia_cheng; }; bool zhuang_bei_compare(const Zhuang_bei & z1, const Zhuang_bei & z2) { return z1.ji_chu_zhan_dou_li > z2.ji_chu_zhan_dou_li; } Zhuang_bei zhuang_bei[MAX]; int main(void) { int n, m; float v, p, q; int i, j, k; cin >> n >> m; for (i = 0; i < n; i++) { cin >> v >> p >> q; zhuang_bei[i].ji_chu_zhan_dou_li = v * (1 + p); zhuang_bei[i].jia_cheng = q; } sort(zhuang_bei, zhuang_bei + n, zhuang_bei_compare); // 1. 基础战斗力优先 float max1 = 0, zui_da_jia_cheng = 0; for (i = 0; i < m; i++) { max1 += zhuang_bei[i].ji_chu_zhan_dou_li; zui_da_jia_cheng = max(zui_da_jia_cheng, zhuang_bei[i].ji_chu_zhan_dou_li * zhuang_bei[i].jia_cheng); } max1 += zui_da_jia_cheng; // 2. 加成值优先 float max2 = 0; zui_da_jia_cheng = 0; for (i = 0; i < m - 1; i++) { max2 += zhuang_bei[i].ji_chu_zhan_dou_li; } for (i = m - 1; i < n; i++) { zui_da_jia_cheng = max(zui_da_jia_cheng, zhuang_bei[i].ji_chu_zhan_dou_li * (1 + zhuang_bei[i].jia_cheng)); } max2 += zui_da_jia_cheng; printf("%.2f\n", max1 > max2 ? max1 : max2); }

结果

未知…

总结

学习如何简化问题