蓝桥杯2022年第十三届C++ C组省赛真题

记录一下傻逼的自己，debug五个小时结果是最后输出没开LL。。。

这题太多坑点了， 可能是做法的问题。

1: 二分x，找到最后一次技能升级最多能提升多少，也有贪心的感觉，

如果最后一次技能升级大于等于m次， 那么就在右区间找（肯定最后一次技能提升的最多，则答案最优）。

2： 有个大坑， 如果一个技能的最后一项刚好等于x的话， 不一定要把他加到答案中，应该记录其出现的次数，等其他最后一项大于x的用完了，如果还有剩余才应该用x。对应看代码： 

#include <iostream>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long LL;

typedef pair<int,int>pii;

const int mod = 1e9 + 7 , INF = 0x3f3f3f3f , N = 1e6 + 10;

int a[N],b[N];

int n,m;

bool check(int x)

{

int cnt = 0;

for (int i = 1 ; i <= n ; i ++)

{

if (a[i] < x) continue;

cnt += 1 + (a[i] - x) / b[i];

if (cnt >= m)

return true;

}

return false;

}

int cc;

int main()

{

cin >> n >> m;

for (int i = 1 ; i <= n ; i ++)

cin >> a[i] >> b[i];

LL res = 0;

// 二分最后一次技能最多提升了多少攻击力

int l = 0,r = 1e6;

while (l < r)

{

int mid = l + r + 1 >> 1;

if (check(mid))

l = mid;

else

r = mid - 1;

}

int x = l;

for (int i = 1 ; i <= n ; i ++)

{

int t = 0;

if (a[i] < x)

continue;

t = (a[i] - x) / b[i] + 1;

if (a[i] - (t - 1) * b[i] == x)

{

t --;

cc ++;

}

if (m >= t)

{

m -= t;

res += (LL)t * (a[i] + a[i] - (t - 1) * b[i]) / 2;

}

else

{

t = m;

m = 0;

res += (LL)t * (a[i] + a[i] - (t - 1) * b[i]) / 2;

break;

}

}

res = res + (LL)min(m,cc) * x;

cout << res << endl;

}