CodeForces - 408B - Garland

小鱼儿 2022-06-12 12:25 146阅读 0赞

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

题目连接：[http://codeforces.com/problemset/problem/408/B][http_codeforces.com_problemset_problem_408_B]

## 题目描述 ##

### Description ###

Once little Vasya read an article in a magazine on how to make beautiful handmade garland from colored paper. Vasya immediately went to the store and bought n colored sheets of paper, the area of each sheet is 1 square meter.

The garland must consist of exactly m pieces of colored paper of arbitrary area, each piece should be of a certain color. To make the garland, Vasya can arbitrarily cut his existing colored sheets into pieces. Vasya is not obliged to use all the sheets to make the garland.

Vasya wants the garland to be as attractive as possible, so he wants to maximize the total area of m pieces of paper in the garland. Calculate what the maximum total area of the pieces of paper in the garland Vasya can get.

一天LMG想画一副关于混子的画，于是他去商店买了n张有颜色的纸，每一张纸的面积都是1平方米。

LMG在脑海中已经有了这副画的构思，由于他是强迫症，他严格将这幅画划分为m个部分，每个部分需要填特定的颜色的纸，必须且仅可以填一张纸。

由于LMG脑子有点问题，他虽然有了构思，但他买纸的时候却买多了（或买少了）纸。但是没关系，他可以将一张纸撕成很多部分，这样可以有很多张这种颜色的纸用于填颜色。

LMG想让这幅画越大越好，所以他想让这幅画的面积最大，计算这幅LMG理想中的画的最大面积。

### Input ###

The first line contains a non-empty sequence of n (1 ≤ n ≤ 1000) small English letters (“a”…”z”). Each letter means that Vasya has a sheet of paper of the corresponding color.

The second line contains a non-empty sequence of m (1 ≤ m ≤ 1000) small English letters that correspond to the colors of the pieces of paper in the garland that Vasya wants to make.

第一行输入包含一个大小为 n (1 ≤ n ≤ 1000) 的非空的字符串。每一个字符都是小写的英文字母(“a”…”z”)。每一个英文字母表示LMG买了哪一种颜色的纸。

第二行输入包含一个大小为 m (1 ≤ m ≤ 1000) 的非空的字符串。每一个字符都是小写的英文字母(“a”…”z”)。每一个英文字母表示LMG需要了哪一种颜色的纸来组成他的画。

### Output ###

Print an integer that is the maximum possible total area of the pieces of paper in the garland Vasya wants to get or -1, if it is impossible to make the garland from the sheets he’s got. It is guaranteed that the answer is always an integer.

输出一个整数表示这幅画的最大面积（要换行），如果完全不能组成输出-1。（保证最终答案一定是一个整数）

### Sample Input ###

aaabbac  
aabbccac

### Sample Output ###

### Sample Input ###

a  
z

### Sample Output ###

\-1

## 解题思路 ##

题意是，给你买的纸，和要用的纸，计算用多少面积。  
如果要用没买输出 -1  
如果 **买的 > 用的** 买多了，实际面积为用的  
如富 **买的 < 用的** 用的多，实际面积为买的（可以根据公式 买的/用的 \* 用的，分成用的份数，然后全用了）  
把字母转化为数字计算，用ascll代码

## AC代码 ##

#include<iostream>

# include #

#include<algorithm>
    using namespace std;
    char str1[1010];
    char str2[1010];
    int a1[30];
    int a2[30];
    int main () {
        int x;
        while(~scanf("%s%s", str1, str2)) {
            int len1 = strlen(str1);
            int len2 = strlen(str2);
            memset(a1, 0, sizeof(a1));
            memset(a2, 0, sizeof(a2));
            for(int i = 0; i < len1; i++) {
                x = str1[i] - 97;
                a1[x]++;
            }
            for(int i = 0; i < len2; i++) {
                x = str2[i] - 97;
                a2[x]++;
            }   
            int sum = 0;
            int flag = 1;
            for(int i = 0; i < 26; i++) {
                if(a1[i] == 0 && a2[i] != 0) {
                    flag = 0;
                    break;
                }
                if(a1[i] >= a2[i]) {
                    sum += a2[i];
                }
                else {
                    sum += a1[i];
                }
            }
            if(!flag) printf("-1\n");
            else printf("%d\n", sum);
        }
        return 0;
    }

[http_codeforces.com_problemset_problem_408_B]: http://codeforces.com/problemset/problem/408/B