更好的阅读体验
蓝桥杯压轴题——技能升级
小蓝最近正在玩一款 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的右侧价值,会使得选择的的个数[HTML_REMOVED]=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分跑路。二分确实难想,需要很深的功力,还得多做多练
类似的题目,数据规模明显小,用堆就足以过掉。
鱼塘钓鱼
有 N 个鱼塘排成一排,每个鱼塘中有一定数量的鱼,例如:N=5 时,如下表:
鱼塘编号 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
第一分钟能钓到的鱼的数量(1…1000) | 10 | 14 | 20 | 16 | 9 |
每钓鱼1分钟钓鱼数的减少量(1..100) | 2 | 4 | 6 | 5 | 3 |
当前鱼塘到下一个相邻鱼塘需要的时间(单位:分钟) | 3 | 5 | 4 | 4 |
即:在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼,第 2 分钟内只能钓到 8 条鱼,……,第 5 分钟以后再也钓不到鱼了。
从第 1 个鱼塘到第 2 个鱼塘需要 3 分钟,从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟,……
给出一个截止时间 T,设计一个钓鱼方案,从第 1 个鱼塘出发,希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关,且每次钓鱼的时间都是整数分钟。
输入格式
共 5 行,分别表示:
第 1 行为 N;
第 2 行为第 1 分钟各个鱼塘能钓到的鱼的数量,每个数据之间用一空格隔开;
第 3 行为每过 1 分钟各个鱼塘钓鱼数的减少量,每个数据之间用一空格隔开;
第 4 行为当前鱼塘到下一个相邻鱼塘需要的时间;
第 5 行为截止时间 T。
输出格式
一个整数(不超过231−1),表示你的方案能钓到的最多的鱼。
数据范围
$1≤N≤100$,
$1≤T≤1000$
输入样例:
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
76
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int,int>PII;
int a[N],b[N],spend[N]; // 分别表示每个鱼塘的第一分钟的鱼数量、公差、到下一个鱼塘的时间
#define x first
#define y second
int n,T;
int main()
{
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) cin>>b[i];
for (int i=2;i<=n;i++)
{
cin>>spend[i];
spend[i]+=spend[i-1]; // 这里用前缀和处理,spend[i]表示为从第一个鱼塘到第i个所需要的时间
}
cin>>T;
int ans = 0; // 答案最少是一条鱼也钓不到
for (int i=1;i<=n;i++) // 枚举最远可以到达的鱼塘是哪一个
{
int fish_time = T - spend[i]; // 求出纯钓鱼时间,即总时间-路上时间
priority_queue<PII>q; // 优先队列模拟堆
for (int k=1;k<=i;k++) // 1~i号鱼塘的鱼数量与编号id入堆
q.push({a[k],k});
int fish=0; // 记录最远到第i号鱼塘所能钓到的鱼数量
while (q.size()&&fish_time>0) // 只要还有时间就可以钓
{
auto t = q.top();
q.pop();
int id = t.y;
fish+=t.x;
fish_time--;
t.x-=b[id]; // 更新下一分钟能钓的数量
if (t.x>0) q.push({t.x,id});
}
ans = max(ans,fish);
}
cout<<ans<<endl;
return 0;
}
小结
这两道题的基本思路和过程很相似,只是因为数据规模的问题,鱼塘这道题不需要再进一步优化了,只需要借助优先队列实现堆,实现取出限制范围内的n个最大值即可;蓝桥杯这道则根据答案具有非严格递减的性质,并且找到了二分的性质,使用二分进行优化。
佬,鱼塘这题能用二分优化吗,二分的最终结果是从1到i,每一个掉多少鱼
orzorz%%%%
蒟蒻谢佬呜呜
不过说实话,技能升级的二分思想真的不太好想,的确是需要很深的功底