宽屏大气通用企业网站源码asp模板源码程序生成静态html,南通海洲建设集团网站,中建八局一公司官网,网站开发项目经验总结教训技能升级 2024-12-10 蓝桥杯每日一题 技能升级 二分 题目大意 一个角色有 N 种可以增加攻击力的技能#xff0c;对于第 i 个技能首次升级可以提升 A i A_i Ai 点攻击力#xff0c;随后的每次升级增加的攻击力都会减少 B i B_i Bi 。升级 ⌈ A i B i ⌉ \lceil \frac{A…技能升级 2024-12-10 蓝桥杯每日一题 技能升级 二分 题目大意 一个角色有 N 种可以增加攻击力的技能对于第 i 个技能首次升级可以提升 A i A_i Ai 点攻击力随后的每次升级增加的攻击力都会减少 B i B_i Bi 。升级 ⌈ A i B i ⌉ \lceil \frac{A_i}{B_i} \rceil ⌈BiAi⌉ 向上取整的次数之后就不会再升级。 最终小蓝可以总计升级 M 次技能计算这个角色最后可以体高多少攻击力 解题思路 以下分为两点来讲解一个 40 分一个100分。 40 分 对于蓝桥杯来说暴力拿分是一定要会的。 对于这个题来说每一个技能的提升都是一个递减的等差数列然后想要在M次升级中让这个角色的攻击力得到最大的提升必须要找到前 M 个大的升级点即可。那么可以通过将这些攻击力的提升点进行一个总的排序然后去前 M 个的总和即可。 但是随着数据量的增加这个排序就会超时。 #include bits/stdc.husing namespace std;
typedef long long ll;vectorint a;bool cmp(int a,int b) {return a b;
}int main()
{int n,m;cinnm;for(int i 1;i n;i) {int aa,bb;cinaabb;int k (aabb-1)/bb;while(k--) {a.push_back(aa);aa - bb;}}sort(a.begin(),a.end(),cmp);ll res 0;for(int i 0;i m;i) {res a[i];}coutresendl;return 0;
}Accepted 继续延续之前的一个思路取前 M 个大的数。那么我们就需要找到第 M 个大的数然后分别找到每一个技能可以升级多少次即可。 那么最关键的就是找到这个第 M 个大的数这时候就引入二分查找来找到这个数这个二分查找类似二分答案的一种但是还要进行一个修改。因为是等差数列所以对于每个数列来说可以通过 O(1) 的时间找到 大于 那个第 M 个大的数的一个数量。 在计算的时候会存在一个边界取值的一个情况我们的处理就是找到所有大于等于 X 的值的一个数量最后会处理多于或者少于 M 次 的边界值个数。 #include bits/stdc.husing namespace std;
const int N 100010;
typedef long long ll;
ll A[N],B[N],n,m;bool check(ll x) {ll cnt 0;for(int i 1;i n;i) {if(A[i] x) continue;ll t (A[i] - x) / B[i];cnt t1;}if(cnt m) return true;else return false;
}int main()
{cinnm;for(int i 1;i n;i) cinA[i]B[i];ll l 0, r 1e610;while(l r) {ll mid (l r 1) 1;if(check(mid)) {l mid;} else r mid - 1;}ll x l;ll cnt 0,sum 0;for(int i 1;i n;i) {if(A[i] x) continue;ll t (A[i] - x)/B[i];if(t*B[i] A[i]-x) t;cnt t;sum (A[i] (A[i] - (B[i]*(t-1))))*t/2;}sum (m-cnt)*x;coutsumendl;return 0;
}备注 想要一起备赛的小伙伴可以看评论区添加讨论群
