题解：AT_pakencamp_2024_day1_b Pakencamp

a_small_OIer · 2026-05-06 21:32:01 · 题解

题目传送门

思路

很显然，购买商品的数量就等于出现最多的字母出现的次数。维护一个桶统计字母出现的次数，然后取最大值即可（特殊的，A 和 P 的出现次数要向上整除以 2）。如果输入数据中包含 P、A、K、E、N、C、A、M、P 以外的字符，输出 -1。

复杂度 O(n)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
int n , ans = 0;
map<char , int> a;
int main(){
    //freopen(".in" , "r" , stdin);
    //freopen(".out" , "w" , stdout);
    scanf("%d" , &n);
    getchar();
    for(int i = 1 ; i <= n ; ++i){
        char c = getchar();
        a[c] += 1;
    }
    for(auto i : a){
        char c = i.first;
        if(c == 'P' || c == 'A')
            ans = max(ans , (int)ceil(i.second / 2));
        else if(c == 'K' || c == 'E' || c == 'N' || c == 'C' || c == 'M')
            ans = max(ans , i.second);
        else{
            printf("-1");
            return 0;
        }
    }
    printf("%d" , ans);
    return 0;
}