csu 1550(字元串處理思路題)

1550: Simple String

Time Limit: 1 Sec Memory Limit: 256 MB

Description

Welcome,this is the 2015 3th Multiple Universities Programming Contest ,Changsha

,Hunan Province. In order to let you feel fun, ACgege will give you a

simple problem. But is that true? OK, let’s enjoy it.

There are three strings A , B and C. The length of the string A is 2*N,

and the length of the string B and C is same to A. You can take N

characters from A and take N characters from B. Can you set them to C ?

Input

There are several test cases.

Each test case contains three lines A,B,C. They only contain upper case letter.

0<N<100000

The input will finish with the end of file.

Output

For each the case, if you can get C, please print “YES”. If you cann’t get C, please print “NO”.

Sample Input

AABB
BBCC
AACC
AAAA
BBBB
AAAA      

Sample Output

YES
NO
題意:給出3個串A B C，長度都為 2*n ,能否在 A 中選n個字元,在B中選n個字元,組成C？題解:我們将A串作為基準串 ,A中每個字元能夠選的最少數量為 max(0,num2[i]-num1[i]) ，能夠選的最多數量為 min(num[i],num2[i]) ,将所有的可能相加,如果 n 在這個範圍内,那麼我們就一定可以在B中選出長度為n的串組成C。      

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N = 100005;
char A[N],B[N],C[N];
int num[30],num1[30],num2[30];
int main()
{
    while(scanf("%s",A)!=EOF){
        scanf("%s",B);
        scanf("%s",C);
        int len = strlen(A);
        memset(num,0,sizeof(num));
        memset(num1,0,sizeof(num1));
        memset(num2,0,sizeof(num2));
        for(int i=0;i<len;i++){
            num[A[i]-'A']++;
            num1[B[i]-'A']++;
            num2[C[i]-'A']++;
        }
        bool flag = true;
        int l = 0,r = 0;
        for(int i=0;i<26;i++){
            if(num[i]+num1[i]<num2[i]){ ///第三個串中某個字元數量 > 一串和二串之和
                flag = false;
                break;
            }
            int MIN = max(0,num2[i]-num1[i]); ///最少可以貢獻的字元數量
            int MAX = min(num[i],num2[i]);  ///最多可以貢獻的字元數量
            l+=MIN;
            r+=MAX;
        }
        if(!(l<=len/2&&r>=len/2)) flag = false;
        if(!flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}