蓝桥杯备赛-二分-技能升级

问题描述

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 NN 个可以加攻击力的技能。

其中第 ii 个技能首次升级可以提升 AiAi​ 点攻击力, 以后每次升级增加的点数 都会减少 Bi。「AiBi⌉Bi​。「Bi​Ai​​⌉ (上取整) 次之后, 再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 MM 次技能, 他可以任意选择升级的技能和次数。请 你计算小蓝最多可以提高多少点攻击力?

输入格式

输入第一行包含两个整数 NN 和 MM 。

以下 NN 行每行包含两个整数 AiAi​ 和 BiBi​ 。

输出格式

输出一行包含一个整数表示答案。

样例输入

3 6
10 5
9 2
8 1

//暴力40%
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct skill {int a;int b;skill(int a,int b) {this->a = a;this->b = b;}
};
bool cmp(skill x, skill y) {if (x.a > y.a) {return true;}else if(x.a == y.a) {//考虑升级技能数的情况return x.b < y.b;}else {return false;}
}
int main() {int n, m;cin >> n >> m;vector<skill> a;int x, y;a.push_back(skill(0, 0));for (int i = 1; i <= n; i++) {cin >> x >> y;a.push_back(skill(x, y));}sort(a.begin()+1, a.begin() + n+1, cmp);//第一个不参与排序long long sum = 0;for (int i = 1; i <= m; i++) {sum += a[1].a;a[1].a -= a[1].b;//第一次升级就要减if (a[1].a < 0) a[1].a = 0;sort(a.begin()+1, a.begin() + n+1, cmp);//第一个不参与排序}cout << sum;return 0;
}

样例输出

47

评测用例规模与约定

对于 40%40% 的评测用例, 1≤N,M≤10001≤N,M≤1000;

对于 60%60% 的评测用例, 1≤N≤104,1≤M≤1071≤N≤104,1≤M≤107;

对于所有评测用例, 1≤N≤105,1≤M≤2×109,1≤Ai,Bi≤1061≤N≤105,1≤M≤2×109,1≤Ai​,Bi​≤106 。