【蓝桥杯每日一题】技能升级

技能升级

题目大意

一个角色有 N 种可以增加攻击力的技能，对于第 i 个技能首次升级可以提升 $A_i$ 点攻击力，随后的每次升级增加的攻击力都会减少 $B_i$ 。升级 $\lceil \frac{A_i}{B_i}\rceil$ （向上取整）的次数之后就不会再升级。

最终小蓝可以总计升级 M 次技能，计算这个角色最后可以体高多少攻击力？

解题思路

以下分为两点来讲解，一个 40 分，一个100分。

40 分

对于蓝桥杯来说，暴力拿分是一定要会的。

对于这个题来说，每一个技能的提升都是一个递减的等差数列，然后想要在M次升级中让这个角色的攻击力得到最大的提升，必须要找到前 M 个大的升级点即可。那么可以通过将这些攻击力的提升点进行一个总的排序，然后去前 M 个的总和即可。

但是随着数据量的增加这个排序就会超时。

#include <bits/stdc++.h>using namespace std;
typedef long long ll;vector<int> a;bool cmp(int a,int b) {return a > b;
}int main()
{int n,m;cin>>n>>m;for(int i = 1;i <= n;i++) {int aa,bb;cin>>aa>>bb;int k = (aa+bb-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];}cout<<res<<endl;return 0;
}

Accepted

继续延续之前的一个思路，取前 M 个大的数。那么我们就需要找到第 M 个大的数然后分别找到每一个技能可以升级多少次即可。
那么最关键的就是找到这个第 M 个大的数，这时候就引入二分查找来找到这个数，这个二分查找类似二分答案的一种，但是还要进行一个修改。因为是等差数列，所以对于每个数列来说可以通过 O(1) 的时间找到 大于 那个第 M 个大的数的一个数量。

在计算的时候，会存在一个边界取值的一个情况，我们的处理就是找到所有大于等于 X 的值的一个数量，最后会处理多于或者少于 M 次 的边界值个数。

#include <bits/stdc++.h>using 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 += t+1;}if(cnt >=  m) return true;else return false;
}int main()
{cin>>n>>m;for(int i = 1;i <= n;i++) cin>>A[i]>>B[i];ll l = 0, r = 1e6+10;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;cout<<sum<<endl;return 0;
}

备注

想要一起备赛的小伙伴可以看评论区添加讨论群！