hdu1004 - Let the Balloon Rise

分手后的思念是犯贱 2022-07-14 14:47 149阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1004][http_acm.hdu.edu.cn_showproblem.php_pid_1004]

# 定位 #

*  字符串处理
 *  STL Map

# 分析 #

*  字符串处理能力，c++明显优于c。
    
    c++提供string类处理字符串，重载了部分运算符，且提供有丰富的内置函数。用c++处理字符串，解题效率较高，对资源限制较小的水题适用。
    
    c没有专门用于处理字符串的机制，c将字符串的处理转变为单个字符的处理，例如，只能采用字符数组或者字符指针存储字符串。用c处理字符串，编程难度稍大，代码执行效率较高，也应该熟练掌握。
 *  解题思路一
    
    创建两个数组存储计算过程：字符串数组ballon，存储颜色名称；整型数组num，存储颜色频数。两数组索引值一一对应，即颜色名称与其出现频数的索引值相同。
 *  解题思路二
    
    本题存储需求为一系列的键值对，采用STL提供的Map关联容器可以满足需求。

# 解题一 #

## 代码 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main()
    {
        int n,s,i;
        int flag;
        int m,pos;
        char ballon[1001][16];
        char num[1001] = {
       0};
        char tmp[16];
        scanf("%d*c",&n);
        while(n)
        {
            s = 0;
            m = 0;
            pos = 0;
            memset(ballon,0,sizeof(ballon));
            memset(num,0,sizeof(num));
            while(n--)
            {
                flag = 0;
                scanf("%s",&tmp);
                for(i=0;i<s;i++)
                {
                    if(strcmp(ballon[i],tmp) == 0)
                    {
                        num[i]++;
                        flag = 1;
                        break;
                    }
                }
                if(flag != 1)
                {
                    strcpy(ballon[s],tmp);
                    num[s]++;
                    s++;
                }
            }
            for(i=0;i<s;i++)
            {
                if(num[i] > m)
                {
                    pos = i;
                    m = num[i];
                }
            }
            printf("%s\n",ballon[pos]);
            scanf("%d*c",&n);
        }
    }

## 性能 ##

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">0MS</td> 
   <td align="center">1424K</td> 
   <td align="center">1083B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

# 解题二 #

## 代码 ##

#include <iostream>
    #include <string>
    #include <map>
    
    using namespace std;
    
    int main()
    {
        map<string,int> ballon;
        string tmp,pos;
        int n,m;
        cin>>n;
        while(n)
        {
            ballon.clear();
            m = 0;
            while(n--)
            {
                cin>>tmp;
                ballon[tmp]++;
            }
            map<string,int>::iterator it;
            for(it=ballon.begin();it!=ballon.end();it++)
            {
                if(it->second > m)
                {
                    m = it->second;
                    pos = it->first;
                }
            }
            cout<<pos<<endl;
            cin>>n;
        }
    }

## 性能 ##

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">0MS</td> 
   <td align="center">1800K</td> 
   <td align="center">624B</td> 
   <td align="center">c++</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

## 字符串数组 ##

c语言中，字符串的存储方式是字符数组或者字符指针。如果有存储字符串数组的需求，就要使用字符型二维数组或者字符指针数组。字符型二维数组，优点是可以方便地修改内容，缺点是存储空间存在浪费。字符指针数组，优点是存储空间100%使用，缺点是存储修改不方便。

> 字符指针存储的只是字符串的地址，字符串存储在堆栈中。必须先有字符串，再用字符指针存储其地址。因此，字符指针标准输入、初始化、修改都不方便。

## 结果唯一性 ##

题设中保证了结果的唯一性，进一步降低了解题难度。若题设中没有此类说明，则须考虑结果不唯一的情况。

> It is guaranteed that there is a unique solution for each test case.

Thanks everyone!

[http_acm.hdu.edu.cn_showproblem.php_pid_1004]: http://acm.hdu.edu.cn/showproblem.php?pid=1004