[Codeforces][Round #734][Div.3] B-1 : Wonderful Coloring - 1 (C++)

https://codeforces.com/contest/1551/problem/B1

Problem - B1 - Codeforces

 

 

[난이도] Div.3
[유형] Greedy

[풀이]
어떤 알파벳이라 2개 이상이라면 레드,그린 각각 1개씩 밖에 들어갈수 없고,
1개만 있는 알파벳들은 어디든지 들어갈 수 있습니다.
이것을 이용하면
답은 (2개 이상인 알파벳의 개수)+(1개만 있는 알파벳의 개수)/2 인것을 알 수 있습니다.

 

 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int tc,n,a,b,cnt[26];
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        memset(cnt,0,sizeof(cnt));
 
        for(char c : s){
            cnt[c-'a']++;
        }
 
        int ans=0,remain=0;
        for(int i=0;i<26;i++){
            if(cnt[i]>=2) ans++;
            else if(cnt[i]==1) remain++;
        }
        printf("%d\n",ans+remain/2);
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/B-1.cpp