【map】【set】poj 3297

1. 每个项目的有效报名人数 --> map<项目名称, 人数> --> map<string, int> mapNum4Prj

2. 局部（当前项目）报名学生 --> set<当前项目学生> --> set<string> setStu4Curr

用于检测当前项目中该学生是否是第一次出现

3. 全局学生报名的第一个项目 --> map<学生, 第一个项目> --> map<string, string> mapFirstPrj

两个作用：

    (1) 用于检测该学生是否已经报名过其它项目

    (2) 记录第一次报名的项目名称，在发现该学生报名第二个项目时将其在报名的第一个项目中剔除，第三次及后续发现该学生时什么也不做

对于一个学生：

检查是否已经在局部(setStu4Curr)存在 -->

    1. 存在 --> do nothing

    2. 不存在 -->

        2.1 检查全局(mapFirstPrj)是否已经存在 -->

            2.1.1 不存在 --> 当前项目人数 +1

                                         mapFirstPrj.insert(<本学生名, 当前项目名>)

            2.1.2 存在 -->

                2.1.2.1 该学生对应的项目名为 "0"(该学生至少是第三次出现，第二个出现时被置 "0")

                                                --> do nothing

                2.1.2.2 该学生对应的项目名非 "0"(该学生第二次出现，此时记录的项目名为第一次的项目名)

                                                --> 对应的项目名人数 -1

                                                      对应的项目名置 "0"

        2.2 将该学生加入当前项目(setStu4Curr)

/*
 * poj 3297
 * http://poj.org/problem?id=3297
 * 1136K	63MS
 * 【map】【set】
 * 1. 为保证效率，最后输出排序时用的是 list, 而非 vector.
 */
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <list>
using namespace std;

#define NULL_PRJ "0"

struct SStuNum4Prj
{
    string  strPrj;
    int     iStuNum;
};

bool operator<(SStuNum4Prj &oL, SStuNum4Prj &oR)
{
    if (oL.iStuNum == oR.iStuNum)
    {
        return (oL.strPrj < oR.strPrj);
    }
    return (oL.iStuNum > oR.iStuNum);
}

typedef map<string, string>::iterator   ItMapStrStr;
typedef map<string, int>::iterator      ItMapStrInt;
typedef list<SStuNum4Prj>::iterator     ItLstSN4Prj;

void Output(map<string, int> &mapNum4Prj)
{
    list<SStuNum4Prj> lstStuNum4Prj(mapNum4Prj.size());
    ItMapStrInt it1 = mapNum4Prj.begin();
    ItLstSN4Prj it2 = lstStuNum4Prj.begin();
    for ( ;it1 != mapNum4Prj.end(); ++it1, ++it2)
    {
        it2->strPrj     = it1->first;
        it2->iStuNum    = it1->second;
    }
    lstStuNum4Prj.sort();
    for (it2 = lstStuNum4Prj.begin();
         it2 != lstStuNum4Prj.end(); ++it2)
     {
         cout << it2->strPrj << " " << it2->iStuNum << endl;
     }
}

int main()
{
    map<string, int>    mapNum4Prj;     // 各项目报名人数
    set<string>         setStu4Curr;    // 当前项目报名学生集合
    map<string, string> mapFirstPrj;    // 某学生第一次报名的项目名
    ItMapStrStr         itMapStrStr;
    ItMapStrInt         itMapStrInt;
    pair<ItMapStrInt, bool> pairCurrPrj;
    string              strTmp;
    string              strCurrPrj;
    while (1)
    {
        getline(cin, strTmp);
        if ('0' == strTmp[0])   // end
        {
            break;
        }
        else if ('1' == strTmp[0])  // current case end
        {
            Output(mapNum4Prj);
            mapNum4Prj.clear();
            mapFirstPrj.clear();
            continue;
        }
        else if ( (strTmp[0] >= 'A') && (strTmp[0] <= 'Z') )    // prj name
        {
            setStu4Curr.clear();
            pairCurrPrj = mapNum4Prj.insert(pair<string, int>(strTmp, 0));
            strCurrPrj  = strTmp;
        }
        else    // student user id
        {
            if (0 == setStu4Curr.count(strTmp)) // 该学生在当前项目中第一次出现
            {
                itMapStrStr = mapFirstPrj.find(strTmp);
                if (mapFirstPrj.end() == itMapStrStr)   // 该学生报名的第一个项目
                {
                    ++( (pairCurrPrj.first)->second);
                    mapFirstPrj.insert(pair<string, string>(strTmp, strCurrPrj));
                }
                else
                {
                    if (itMapStrStr->second != NULL_PRJ)
                    {
                        --mapNum4Prj[itMapStrStr->second];
                        itMapStrStr->second = NULL_PRJ;
                    }
                }
                setStu4Curr.insert(strTmp);
            }
        }
    }

    return 0;
}