Asyc

用户名：FlyZZZ

访问量：1358

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

C语言训练-最大数问题（C语言代码）.........关于-1

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

（二分）技能升级

　　作者: Asyc　　　　发表时间：2022-04-16 17:52:59 浏览：1252　|　评论：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 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

　　评论区

wjy

2022-04-23 16:35:49

jeb0813

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

2022-04-19 21:04:42

Asyc

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

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

C语言训练-最大数问题（C语言代码）.........关于-1

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

C二级辅导-阶乘数列（C语言代码）

（二分）技能升级

评论区

精彩推荐

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

【回文数(二)】（C语言代码）

简单的a+b （C语言代码）

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

printf基础练习2 （C语言代码）

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

简单的a+b （C语言代码）

【明明的随机数】（C语言代码）

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

【计算直线的交点数】（C语言代码）

Asyc

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

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

C语言训练-最大数问题 （C语言代码）.........关于-1

C语言训练-舍罕王的失算 （C++代码）（都给答案了还算什么）

C二级辅导-阶乘数列 （C语言代码）

（二分）技能升级

评论区

精彩推荐

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

【回文数(二)】 （C语言代码）

简单的a+b （C语言代码）

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

printf基础练习2 （C语言代码）

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

简单的a+b （C语言代码）

【明明的随机数】 （C语言代码）

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

【计算直线的交点数】 （C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

C二级辅导-阶乘数列（C语言代码）

　　评论区

【回文数(二)】（C语言代码）

【明明的随机数】（C语言代码）

【计算直线的交点数】（C语言代码）