ACM 水果 hdu 1263 一题多解

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1263

文章末有相应的一些测试数据供参考。

传统的数组解题方式

思路一：

三种属性的数据放在一个结构体里面，然后按照题目要求排序。

输出处理的时候，遍历一遍，边统计边输出，因为排序并没有进行统计。

思路二：

同样是一个结构体，然后排序。

再做一个预处理——遍历一遍，如果产地和品种都一样，将数目加在后者上面，前者数目清零

将处理好的数组直接遍历输出（一个for循环里面两个 if 分别控制输出两类数据）：

如果当前产地和前一个的产地不一样，输出产地

如果当前元素中水果数量不为零，输出水果信息

代码如下

两种思路前面的代码都一样：

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 using namespace std;
 5 struct INFO
 6 {
 7     string area, fruit;
 8     int num;
 9 }info[102];
10 
11 inline bool my_cmp(const INFO& lhs, const INFO& rhs) 
12 {
13     if (lhs.area == rhs.area)
14         return lhs.fruit < rhs.fruit;
15     return lhs.area < rhs.area;
16 }

思路一main函数代码：

int main()
{
    int group;
    cin >> group;
    while (group--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> info[i].fruit >> info[i].area >> info[i].num;
        sort(info, info + n, my_cmp);
        for (int i = 0; i < n; ++i)
        {
            cout << info[i].area << endl;
            bool key = false;
            while (i + 1 < n&&info[i + 1].area == info[i].area)  //如果产地一样
            {
                if (key) {
                    i++;                                         //i 加了 1
                    if (info[i + 1].area != info[i].area) {      //下一个的产地可能和当前的产地不一样
                        cout << "   |----" << info[i].fruit << "(" << info[i].num << ")" << endl;
                        break;
                    }
                }
                key = true;
                int number = info[i].num;
                while (i + 1 < n&&info[i + 1].fruit == info[i].fruit) //如果水果一样
                {
                    i++;
                    number += info[i].num;
                }
                cout << "   |----" << info[i].fruit << "(" << number << ")" << endl;
            }
            if (!key)
                cout << "   |----" << info[i].fruit << "(" << info[i].num << ")" << endl;
        }
        if (group)cout << endl;
    }
}

思路二main函数代码：

 1 int main() {
 2     int Group, m;
 3     cin >> Group;
 4     while (Group--) {
 5         int j = 0;
 6         cin >> m;
 7         for (int i = 0; i < m; i++)
 8             cin >> info[i].fruit >> info[i].area >> info[i].num;
 9         sort(info, info + m, my_cmp);
10         //再次预处理
11         for (int i = 1; i<m; i++){
12             if (info[i].area==info[i-1].area&&info[i].fruit==info[i-1].fruit){  
13                 info[i].num += info[i - 1].num;
14                 info[i - 1].num = 0;
15             }
16         }
17         cout << info[j].area << endl;
18         for (j = 0; j<m; j++){
19             if (j != 0 && info[j].area != info[j - 1].area) //只要产地不一样就输出产地信息
20                 cout << info[j].area << endl; 
21             if (info[j].num != 0)                           //只要数量不为0就输出水果信息                
22                 cout << "   |----" << info[j].fruit << "(" << info[j].num << ")" << endl;
23         }
24         if (Group) cout << endl;                            //只要不是最后一组数据就打一个空行
25     }
26     return 0;
27 }

STL中map嵌套解题方式

其思路同二，只不过map不需要分类

（代码转自：http://blog.csdn.net/u012861385/article/details/19038865）

 1 #include<iostream>  
 2 #include<map>  
 3 #include<string>  
 4 using namespace std;  
 5 int main()  
 6 {  
 7     int N, M;  
 8     int i,j,k;  
 9     string name, place;  
10     int value;  
11     scanf("%d", &N);  
12     while(N--)  
13     {  
14         map<string,map<string, int> > str;                 //先按地点，第一个string排序插入，之后按照第二个string名称排序插入//  
15         map<string,map<string, int> >::iterator it;  
16         map<string,int>::iterator iw;  
17         scanf("%d", &M);  
18         for(i = 1; i <= M; i++)  
19         {  
20             cin >> name >> place >> value;  
21             str[place][name] += value;  
22         }  
23         for(it = str.begin(); it != str.end(); it++)  
24         {  
25             cout << it->first <<endl;  
26             for(iw = it->second.begin(); iw != it->second.end(); iw++)  
27             {  
28                 cout<<"   |----"<<iw->first<<"("<<iw->second<<")"<<endl;  
29             }  
30         }  
31         if(N != 0)  
32             cout << endl;  
33     }  
34     return 0;  
35 }

参考数据（本人）：http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=34666&messageid=1&deep=0

对应的output如下

1
   |----a(2)
   |----b(2)
   |----c(1)
   |----d(3)
2
   |----a(2)
   |----b(1)
   |----c(2)
   |----d(1)

1
   |----a(1)
2
   |----a(1)
   |----b(1)
3
   |----b(1)

谢谢您的阅读，祝您生活愉快~