蓝桥杯2022年第十三届C++ C组省赛真题-技能升级

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

。

。

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

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

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

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

对应看代码： 

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pairpii;
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;
}