Asyc

用户名：FlyZZZ

访问量：1238

签　名：

等　　级
排　　名	37898
经　　验	355
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

（二分）技能升级
浏览：1154

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

（二分）技能升级

　　作者: Asyc　　　　发表时间：2022-04-16 17:52:59 浏览：1154　|　评论：2　

原题链接：蓝桥杯2022年第十三届省赛真题-技能升级

## 技能升级

### 题目描述
小蓝最近正在玩一款 `RPG` 游戏。他的角色一共有 `N` 个可以加攻击力的技能。其中第 `i` 个技能首次升级可以提升 `Ai` 点攻击力，以后每次升级增加的点数都会减少 `Bi`。技能升级(上取整) 次之后，再升级该技能将不会改变攻击力。

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

### 题目思路
> 二分搜索出要拿的M个数中最小的那个数，每次check x 再用二分搜索n组数中每组 >= x的数有多少个，如果总数 >= m ， 说明 x 可以增大， 否则 x 减小

### 参考代码

```cpp
#include<bits/stdc++.h>
#define pw(a) (1LL<<(a))
#define L ((p)<<1)
#define R ((p)<<1|1)
#define endl '\n'
#define int long long
using namespace std;
 
typedef long long LL;
typedef double DD;
typedef pair<int,int> PAIR;
 
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=5e5+10;
 
int n,m,t,ans,cnt,sum;
int a[N],b[N],k[N];
 
#undef L
#undef R
inline bool check(int x)
{
	LL cnt=0;
	for(int i=1;i<=n;i++)
	{
		int l=0,r=k[i]+1;
		while(r-l>1)
		{
			int mid=l+r>>1;
			if((a[i]-(mid-1)*b[i])>=x) l=mid;
			else r=mid;
		}
		cnt+=l;
	}
	return cnt>=m;
}
signed main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		k[i]=(a[i]+b[i]-1)/b[i];
	}
	int l=0,r=*max_element(a+1,a+n+1)+1;
	while(r-l>1)
	{
		int mid=l+r>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	int x=l,cnt=0;
	LL ans=0;
	// cout<<x<<endl;
	// vector<int>v;
	for(int i=1;i<=n;i++)
	{
		int l=0,r=k[i]+1;
		while(r-l>1)
		{
			int mid=l+r>>1;
			if((a[i]-(mid-1)*b[i])>=x) l=mid;
			else r=mid;
		}
		// cout<<l<<' '<<k[i]<<endl;
		// cout<<a[i]<<' '<<l<<' '<<k[i]<<' '<<a[i]-(l-1)*b[i]<<endl;
		ans+=l*a[i]-l*(l-1)/2*b[i];
		// if(l) v.push_back(a[i]-(l-1)*b[i]);
		cnt+=l;
	}
	// for(int i=1;i<=n;i++) cout<<k[i]<<endl;
	// cout<<accumulate(k+1,k+n+1,0LL)<<endl;
	// sort(v.begin(),v.end());
	// for(int x:v) cout<<x<<endl;
	// cout<<l<<' '<<cnt<<endl;
	ans-=(cnt-m)*l;
	cout<<ans<<endl;
	return 0;
}
```

0.0分

21 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

wjy

2022-04-23 16:35:49

jeb0813

大佬为什么我用堆做的会TLE

2022-04-19 21:04:42

Asyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C二级辅导-求偶数和（C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

字符串比较（C语言代码）答案错误？？？？

（二分）技能升级

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-大、小写问题（C语言代码）

简单的for循环

母牛的故事（C语言代码）

钟神赛车（C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

幸运数（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

Asyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C二级辅导-求偶数和 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

字符串比较 （C语言代码）答案错误？？？？

（二分）技能升级

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

简单的for循环

母牛的故事 （C语言代码）

钟神赛车 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

幸运数 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C二级辅导-求偶数和（C++代码）

字符串比较（C语言代码）答案错误？？？？

　　评论区

C语言训练-大、小写问题（C语言代码）

母牛的故事（C语言代码）

钟神赛车（C语言代码）

幸运数（C++代码）