蓝桥杯压轴题——技能升级
小蓝最近正在玩一款 RPG 游戏。
他的角色一共有 N 个可以加攻击力的技能。
其中第 i 个技能首次升级可以提升 \(A_i\) 点攻击力，以后每次升级增加的点数都会减少 \(B_i\)。
\(⌈\frac{A_i}{B_i}⌉\)（上取整）次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。
请你计算小蓝最多可以提高多少点攻击力？
输入格式
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 \(A_i\) 和 \(B_i\)。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40% 的评测用例，\(1≤N,M≤1000\)；
对于 60% 的评测用例，\(1≤N≤10^4\)，\(1≤M≤10^7\)；
对于所有评测用例，\(1≤N≤10^5\)，\(1≤M≤2×10^9\)，\(1≤A_i,B_i≤10^6\)。
输入样例：
3 6
10 5
9 2
8 1
输出样例：
47
朴素做法——借助优先队列实现堆
题目意思很清晰了，就是选择m个最大的数值。同时我们注意到每个技能都是构成了一个等差数列，每个等差数列都是首项为a[i],公差为-b[i]的递减等差数列。那么很自然的做法就是，把所有的等差数列扔到一个集合中，从大到小选取前m大的数，即可完成题目
选取前m大的数，比较好的实现方式就是借助多路归并的思想，借助优先队列实现堆（默认就是大根堆）即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
priority_queue<PII>heap;
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
heap.push({a[i],i});
}
LL ans = 0;
while (m--)
{
ans+=heap.top().x;
int id = heap.top().y;
heap.pop();
a[id]-=b[id];
heap.push({a[id],id});
}
cout<<ans<<endl;
return 0;
}
很容易分析这种解法的复杂度为\(O(mlogn)\)，显然会超时。分析超时原因，就是因为m太大，达到了\(2*10^9\)的级别，因此需要进一步优化。要想在\(10^8\)以内AC掉，显然需要把m降成logm或者直接复杂度与m无关，只与n有关。
优化解法
我们可以发现，如果是m次枚举，必然还会超时。那么就想如何与m无关。通过模拟样例我们发现，最终的选择序列为10 9 8 7 7 6,当前选择的数一定不大于（小于或者等于）上一个选择的数，那么选择的序列就构成了一个非严格单调下降的序列。我们会想到二分，但还不能完全确定，需要满足一下二分的几个性质和要求。现在只满足了二分的单调性。
接下来看看是否满足二段性以及可以二分的性质是什么。是否满足二段性以及二段性的性质是什么一般是一起想。
假设答案为t，即t的含义为：能选择的最后的技能价值。则t的左侧的价值，会使得选择的个数>=m,t的右侧价值，会使得选择的的个数<m。因此具有二段性，同时二段性的性质就是当前价值能选择的数量与m的关系。若当前二分的数满足可选择数量>=m，则l=mid，目的是让最后可选的价值大一些，这样就可以让可选的数量小一些；若当前二分的数满足可选数量<m，则r=mid-1，目的是让最后可选的价值小一些，这样就可以让可选的数量大一些。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];
typedef long long LL;
int n,m;
bool check(int mid)
{
LL cnt = 0;
for (int i=1;i<=n;i++)
{
if (a[i]>=mid)
cnt+=(a[i]-mid)/b[i]+1;
}
return cnt>=m;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i]>>b[i];
int l=0,r=1e6;
while (l<r)
{
int mid = l+r+1>>1;
if (check(mid)) l=mid;
else r= mid-1;
}
LL ans = 0,cnt=0; // cnt>=m
for (int i=1;i<=n;i++)
{
if (a[i]>=r)
{
int t = (a[i]-r)/b[i]+1;
cnt+=t;
int end = a[i]-(t-1)*b[i];
ans+=1ll*t*(a[i]+end)/2;
}
}
cout<<ans-(cnt-m)*r<<endl; // 去掉>m的部分
return 0;
}
总结
这道题估计在考场就直接\(O(mlogn)\)的堆实现了，拿到40分跑路。二分确实难想，需要很深的功力，还得多做多练
标签：10,cnt,int,每日,mid,heap,技能 From： https://www.cnblogs.com/sdnu-dfl/p/17039740.html