水果(STL+排序）- HDU 1263
作者：AlphaWA
Problem Description
夏天来了~~好开心啊,呵呵,好多好多水果~~ Joe经营着一个不大的水果店.他认为生存之道就是经营最受顾客欢迎的水果.现在他想要一份水果销售情况的明细表,这样Joe就可以很容易掌握所有水果的销售情况了.
Input
第一行正整数N(0<N<=10)表示有N组测试数据. 每组测试数据的第一行是一个整数M(0<M<=100),表示工有M次成功的交易.其后有M行数据,每行表示一次交易,由水果名称(小写字母组成,长度不超过80),水果产地(小写字母组成,长度不超过80)和交易的水果数目(正整数,不超过100)组成.
Output
对于每一组测试数据,请你输出一份排版格式正确(请分析样本输出)的水果销售情况明细表.这份明细表包括所有水果的产地,名称和销售数目的信息.水果先按产地分类,产地按字母顺序排列;同一产地的水果按照名称排序,名称按字母顺序排序. 两组测试数据之间有一个空行.最后一组测试数据之后没有空行.
Sample Input
1
5
apple shandong 3
pineapple guangdong 1
sugarcane guangdong 1
pineapple guangdong 3
pineapple guangdong 1
Sample Output
guangdong
|----pineapple(5)
|----sugarcane(1)
shandong
|----apple(3)
这次是中文题目，就免得我翻译了，大家理解起来很容易。
思路：
其实只要了解一下map和pair的排序知识，他怎么说你怎么做就行了……STL中的map，它是map<key,value>形式的存在，像一个映射一样。它内部默认实现对于key的从小到大排序。而pair<first,second>我们不止一次地提到过了，先排first后排second。他题里面要求两个部分进行排序，一个是产地按字典序，一个是水果名称按字典序，其实就是字符串的从小到大排序。虽然怎么搞都可以，不过对于映射关系的构造（即哪个东西当first哪个东西当second）会影响代码复杂度。此处AlphaWA的思路是构造map<pair<水果产地，水果名称>,水果数量>，这样map的key就是pair<产地，名称>，value就是数量，数量是不用排序的，排序先排产地后排名称，符合题意，酱紫我们只遍历一遍map里的元素并输出就可以辣！
PS1：以这个为例，如果想要map降序而不是由小到大的话，和其他容器一样，只要map<P,int,greater<P> >即可（此处以P指代pair<string,string>）。更多其他自定义的map排序我也不会，感兴趣的同学可以自己搜索相关资料。
PS2：初学STL需要遇见的时候记一记这个容器是怎么用的，下次有机会就用一下，慢慢就能掌握一些基本操作了。
代码如下：
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
#include<utility>
using namespace std;
typedef pair<string,string>P;//接下来用P代表pair<string,string>，免得每次都写那么长了
map<P,int>m;//map<pair<水果产地，水果名称>,水果数量>
int main()
{
int test,n;
string s,t;
scanf("%d",&test);
while(test--)
{
m.clear();
//输入
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int z;
cin>>s>>t>>z;//水果名称、水果产地、数量
if(m.find(P(t,s))!=m.end())//如果已存在则往上加
m[P(t,s)]+=z;
else//否则制造这对儿
m[make_pair(t,s)]=z;
}
string q="";//一个临时的记录
//map已经排好了序直接放迭代器即可
for(map<P,int>::iterator it=m.begin();it!=m.end();it++)
{
//s取出此时的地点、t取出此时的水果
s=it->first.first,t=it->first.second;
//x取出此时的水果数量
int x=it->second;
if(q!=s)//如果出现了新的产地，就要输出，每个产地只要输出一次
{
q=s;
printf("%s\n",s.c_str());//将string用printf输出的方法
}
printf(" |----%s(%d)\n",t.c_str(),x);//输出水果及其数量
}
if(test) printf("\n");//题目要求的输出格式
}
return 0;
}