牛客小白月赛85

A. ACCEPT

思路：

• ACCEPT中每个字符的个数取最小值(C的个数要除以2)

时间复杂度：$O(n)$

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    std::map<char, int> cnt;
    for (auto x : s) {
        cnt[x]++;
    }

    std::cout << std::min({cnt['A'], cnt['C'] / 2, cnt['E'], cnt['P'], cnt['T']}) << "\n";
}

B. 咕呱蛙

思路：

• 打表找规律即可，代码的下面有注释打表的过程，${\mathrm{\Sigma }}_{i=1}^n{\mathrm{\Sigma }}_{j=1}^i$ 的每一项和是两个奇数两个偶数互相交替出现的，然后可以直接得出规律
• $n$ 为奇数，$ans=n\times 2$
• $n$ 为偶数，$ans=n\times 2+1$​

时间复杂度：$O(1)$

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 n;
    std::cin >> n;

    i64 ans = -1;
    if (n % 2 == 0) {
        ans = n * 2;
    } else {
        ans = n * 2 + 1;
    }
    std::cout << ans << "\n";

    return 0;
}
/*
1 2 3 4  5  6  7  8  9  10 11 12 13 14  15  16  17  18  19  20
1 3 6 10 15 21 28 36 47 57 68 80 93 107 122 138 155 173 192 212
*/

C. 得分显示

思路：

• 答案为 ${\mathrm{\Sigma }}_{i=1}^{n}min((a_i+1)÷i)$

附：$a_i+1$​ 即为当前这个数的右极限

时间复杂度：$O(n)$

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    double x = 2e9;
    for (int i = 0; i < n; i++) {
        x = std::min(x, (a[i] + 1) * 1.0 / (i + 1));
    }
    std::cout << x << "\n";

    return 0;
}

D. 阿里马马与四十大盗

思路：

• 会发现只需要维护当前位置的后缀和即可
• 如果当前位置的后缀和大于当前的血量，并且当前的血量不是满的，那么一定是越早回复花费的时间越少
• 注意要判断当前位置是否等于0

时间复杂度：$O(n)$

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }

    i64 b = m, t = n - 1;
    for (int i = 0; i + 1 < n; i++) {
        i64 suf = s[n] - s[i + 1];

        if (b != m && b - suf <= 0 && a[i] == 0) {
            t += m - b;
            b = m;
        }
        if (b - a[i + 1] > 0) {
            b -= a[i + 1];
        } else {
            std::cout << "NO\n";
            return 0;
        }
    }
    std::cout << t << "\n";

    return 0;
}

E. 烙饼

思路：

• 可以发现，我们需要维护一个可以在最短时间内完成尽可能多的饼
• 那么一定要确定一个时间的最大值 $max(\lceil \frac{{\mathrm{\Sigma }}_{i=1}^n{a}_i}{m}\rceil ,max(a_i))$
• 然后维护这最大值即可

时间复杂度：$O(n)$

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    i64 mx = *max_element(a.begin(), a.end());
    i64 sum = std::accumulate(a.begin(), a.end(), 0ll);

    int tot = 1; i64 now = 0;
    mx = std::max((sum + m - 1) / m, mx);
    std::vector<std::array<i64, 4>> ans;
    for (int i = 0; i < n; i++) {
        if (a[i] + now <= mx) {
            ans.push_back({i + 1, tot, now, now + a[i]});
            now += a[i];
            if (now == mx) {
                tot++, now = 0;
            }
        } else {
            ans.push_back({i + 1, tot, now, mx});
            a[i] -= (mx - now);
            tot++, now = a[i];
            ans.push_back({i + 1, tot, 0, now});
        }
    }

    std::cout << ans.size() << "\n";
    for (auto [a, b, c, d] : ans) {
        std::cout << a << " " << b << " " << c << " " << d << "\n";
    }

    return 0;
}