目录

一、题目

1、原题链接

2、题目描述

二、解题报告

1、思路分析

2、时间复杂度

3、代码详解 

三、知识风暴

1、贪心算法

2、归并算法

3、二分查找法

一、题目

1、原题链接

4656. 技能升级 - AcWing题库

2、题目描述

小蓝最近正在玩一款 RPG 游戏。

他的角色一共有 N 个可以加攻击力的技能。

其中第 i个技能首次升级可以提升 Ai点攻击力，以后每次升级增加的点数都会减少 Bi。

⌈Ai/Bi⌉（上取整）次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。

请你计算小蓝最多可以提高多少点攻击力？

输入格式

输入第一行包含两个整数 N 和 M。

以下 N 行每行包含两个整数 Ai 和 Bi。

输出格式

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

数据范围

对于 40% 的评测用例，1≤N,M≤1000；
对于 60% 的评测用例，1≤N≤10^4，1≤M≤10^7；
对于所有评测用例，1≤N≤10^5，1≤M≤2×10^9，1≤Ai,Bi≤10^6。

输入样例：

3 6
10 5
9 2
8 1

输出样例：

47

二、解题报告

1、思路分析

原始思路：

1）每次贪心选择提升攻击力最高的进行升级，即可以将每次可升级的攻击力存到一个multiset中，然后选择最后M项作为M次升级的方法，对后M项求和即为最多提升的攻击力。

2）该方法时间复杂度为O(n^2)，所以必超时（十个测试数据过了四个），但并没有想出优化方法。

标准思路：

思路来源：AcWing 4656. 技能升级（寒假每日一题2023） - AcWing

y总yyds

1）原始思路中因为我们每次都选择的是提升攻击力最多的，我们可以假设每个技能每次所能增加的攻击力是一个递减的等差数列，而我们每次都是选择最大的，也就是从这N个等差序列的头部进行选择，所以我们每次都是能够保证是从最初的技能开始一步步升级的，不会越级升级，因为针对某个技能在把它升到下一级之前，它一定是已经达到了下一级的前一个级别，因为我们每次都选择攻击力提升幅度最大的技能进行升级，而针对某个技能，它的攻击力提升是逐渐下降的，所以我们按照原贪心思路得到的解一定是正确的，下面我们需要对这个算法实现方法进行优化。

2）针对原始思路，我们需要求升序序列前M项的总和，我们直接暴力求肯定超时，我们可以在该 序列中找到某个数x前面正好存在M项，而这个x在该序列中可能存在多个，我们经过分析可知，这个x必定满足：在该序列中大于等于x的数的个数一定大于等于M个，而大于等于x+1的数的个数一定小于M个，而我们可以通过二分查找来查找x。

3）在找到x后，我们可以通过分析，将每个技能的每次升级的攻击力序列视为N个等差序列，根据等差序列的性质我们可知，假设其中某个等差序列首项为a0，公差为-d，则该序列中大于等于x的数的个数为𠃊（a-x）/b𠃎+1个（（a-x）/b下取整+1个），所以我们之后也可以根据等差数列求和公式来计算每个序列大于等于x的数的代数和，最后用这个和减去和x相等的数的总和即为所求结果。

4）模拟上述过程，输出结果，即为所求。

2、时间复杂度

原始思路时间复杂度为O(n^2)

标准思路时间复杂度O(nlogn)

3、代码详解 

原始思路代码：

#include 
#include 
using namespace std;
int A[1000100],B[1000100];
int main() {multisets;int N,M;cin>>N>>M;for(int i=0;i>A[i]>>B[i];for(int j=0;j

#include 
using namespace std; 
int A[100010],B[100010];
int N,M;
//判断大于等于mid的数的个数是否有M个 
bool check(int mid){long long res=0;for(int i=0;i=mid){res+=(A[i]-mid)/B[i]+1;}}return res>=M;
} 
int main()
{  cin>>N>>M;for(int i=0;i>A[i]>>B[i];} int l=0,r=1e6;//二分从0开始，因为0可能为第M个数 while(l>1;//因为下一步l=mid，所以要上取整 if(check(mid)) l=mid;   //如果大于等于mid的数的个数有大于等于M个，则答案在[mid,1e6] else r=mid-1;}long long res=0,cnt=0;//cnt代表总项数 for(int i=0;i=r){int c=(A[i]-r)/B[i]+1;//每个序列中大于r（x）的项数int end=A[i]-(c-1)*B[i];cnt+=c;res+=(long long)(A[i]+end)*c/2;//每个等差数列中大于r（x）的总和}} cout<