找规律 B - Palindrome-phobia（CODE FESTIVAL 2017 Final）

我会带着你远行 2022-06-05 11:15 177阅读 0赞

今天学姐生日，嗨了一天后发现AtCoder开了三场比赛？？

一脸懵逼之后开启补题模式...

这题想了很久，大佬指点了一下懂了...

（向大佬低头...

## B - Palindrome-phobia ##

--------------------

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

### Problem Statement ###

Snuke has a string *S* consisting of three kinds of letters: `a`, `b` and `c`.

He has a phobia for palindromes, and wants to permute the characters in *S* so that *S* will not contain a palindrome of length 2 or more as a substring. Determine whether this is possible.

### Constraints ###

*  1≤|*S*|≤105
 *  *S* consists of `a`, `b` and `c`.

--------------------

### Input ###

Input is given from Standard Input in the following format:

### Output ###

If the objective is achievable, print `YES`; if it is unachievable, print `NO`.

### Sample Input 1 ###

Copy

abac

### Sample Output 1 ###

Copy

YES

As it stands now, *S* contains a palindrome `aba`, but we can permute the characters to get `acba`, for example, that does not contain a palindrome of length 2 or more.

--------------------

### Sample Input 2 ###

Copy

aba

### Sample Output 2 ###

Copy

--------------------

### Sample Input 3 ###

Copy

babacccabab

### Sample Output 3 ###

Copy

YES

思路:现出现的次数最多的字符与其他两个字符数量的差不能大于1

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std; 
    char s[100010];
    int a[10];
    int main()
    {
    	while(scanf("%s",s)!=EOF)
    	{
    		int flag=1;
    		memset(a,0,sizeof(a));
    		for(int i=0;i<strlen(s);i++)
    		a[s[i]-'a']++;		
    		sort(a,a+3);
    		if(a[2]-a[0]>1) 
    		flag = 0;
    		if(a[2]-a[1]>1) 
    		flag = 0;
    		if(flag) 
    		printf("YES\n");
    		else 
    		printf("NO\n");
    	}
    	return 0;
    }