A40888. 技能升级本题总分：25 分【问题描述】小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。⌈ Ai Bi⌉ (上取整) 次之后，再升级该技能将不会改变攻击力。现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？【
填空题
困难
知识点
题目描述
技能升级
本题总分：25 分
【问题描述】
小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技
能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数
都会减少 Bi。⌈ Ai Bi⌉ (上取整) 次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请
你计算小蓝最多可以提高多少点攻击力？
【输入格式】
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 Ai 和 Bi。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
3 6
10 5
9 2
8 1
【样例输出】
47
参考答案
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
int n,m;
const int N=1e5+5;
int c[N],cnt[N];
#define x first
#define y second
typedef pair<int,pair<int,int> > PII;
pair<int,pair<int,int> > a[N];
int main(){
cin >> n >> m;//m是可以升级的次数
int ans=0;
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i].x,&a[i].y.x);
if(a[i].x%a[i].y.x==0)a[i].y.y=a[i].x/a[i].y.x;
else a[i].y.y = a[i].x/a[i].y.x + 1;
}
sort(a+1,a+n+1,greater<PII>() );
for(int i=1;i<=m;++i){
ans+=a[1].x;
a[1].x-=a[1].y.x;
cnt[a[1].x]++;
if(cnt[a[1].x]>=a[1].y.y)a[1].x=0;
sort(a+1,a+n+1,greater<PII>());
}
cout<<ans;
return 0;
}
上一题
下一题