2022牛客寒假算法基础集训营2

A.小沙的炉石 思路

有 n n n张法术进攻牌，每张牌耗费 1 1 1法力，造成 1 1 1伤害(基础伤害)；有 m m m张回复牌，每张牌回复 1 1 1法力。

初始 1 1 1法力，每次使用法术进攻牌后，会增加 1 1 1法术伤害(与基础伤害一起构成实际伤害)。问能否恰好造成总伤害 = k =k =k。

首先观察数据范围，显然 O ( n ) O(n) O(n)的算法无法满足，那么考虑如何检验

首先，我们可以确定，可以造成的攻击伤害位于一个区间内，那么我们需要求解的便是如何确定区间，也就是确定造成伤害的最小值和最大值。

• 对于 a < = b + 1 a b + 1 a>b+1，显然多余部分的攻击卡牌无法使用。
• 可以发现，每将一张回复牌向前与攻击牌交换一次，伤害就会增加 1 1 1，如果我们先用掉全部的回复牌，那么就可以达到最大的伤害效果 a b + a × ( a + 1 ) 2 ab + \frac{a \times (a + 1)}{2} ab+2a×(a+1)​。

但是需要额外注意，当 m = 1 , 2 m = {1, 2} m=1,2时需要特判

Accepted Code

#include 
#define int long long
using namespace std;

inline void solve(){
    int n, a, b;
    cin >> n >> b;
    a = min(b + 1, n);
    int maxx = ((1 + 2 * b + a) * a) >> 1;
    int k, x;
    cin >> k;
    while (k--){
        cin >> x;
        if ((b == 1 && x == 3) || (b == 2 && x == 8)) cout /]})";

inline void solve(){
    int n, m; cin >> n >> m;
    string ans;
    if (n == m && n == 1) cout  1) cout