技能升级(二分+多路归并+贪心)蓝桥杯

技能升级

解题思路

1、首先每一个技能否是一个等差数列

2、最多可以加m次,所以肯定加的次数越多越好

3、一共n个等差数列,所以每次优先在n个等差数列中,选择最大的一项升级(贪心+多路归并思想)

4、需要二分出来加入的第m项攻击力是多少。

5、需要在O(n)复杂度处理多路归并,所以在计算一个等差数列有多少项满足a[i]>=x (x为二分枚举的第m次攻击力) 计算公式为 (a[i]-x)/b+1 (b等差数列的差)

6、最后二分出来的x,可能导致最后加入的个数大于m,因为可能有相等情况,所以要减去多出来的个数乘以x

#include <bits/stdc++.h>
#define ll long longusing namespace std;
typedef pair<int,int>PII;const int N=1e5+10;
int n,m,ans;
int b[N],a[N];int check(int mid) {ll res=0;//统计加入多少项for(int i=1; i<=n; i++) {if(a[i]>=mid) {res+=(a[i]-mid)/b[i]+1;//统计出第i个等差数列有多少个元素大于等于mid}}return res>=m;//如果大于m证明mid可以取,如果小于m证明mid太大了
}int main() {cin>>n>>m;for(int i=1; i<=n; i++)cin>>a[i]>>b[i];int l=0,r=1e6; //每个技能最大攻击力为le6//二分找出第m项的攻击力while(l<r) {int mid=l+r+1>>1;//l=mid所以二分要加上1,如果时r=mid则不用加 if(check(mid))l=mid;//mid可取else r=mid-1;//mid太大了不合法}ll res=0,cnt=0;//res记录最后的攻击力和,cnt统计多少项满足大于二分出的攻击力for(int i=1; i<=n; i++) {if(a[i]>=r) {int k=(a[i]-r)/b[i]+1;//第i项等差数列满足大于二分结果的个数int end=a[i]-(k-1)*b[i];//第n项结果cnt+=k;res+=(ll)(a[i]+end)*k/2;//等差数列求和}}cout<<res-(cnt-m)*r<<endl;//别忘记减去多出来的的项return 0;
}