STL（pair map set vector priority_queue） poj 3297

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

POJ 3297

算法竞赛初级杂烩包

题意：学生选课，没个学生只能选一门课。大写字符是课的名字，小写是人名。如果课程后面有多个相同名字算一个，如果一个人选多门课，则他选不上课，输出课和每门课选课人数

思路：

map<string,set<int> > stu：一个学生名对应他选了哪几门课

map<string,ser<int> > pro：课程名对应有几个学生选了他，set存对应的学生

vector<pair<int,string> > ans：最后结果，课程名对应所选学生人数

a[]：判断一个学生是否只选了一门课

 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <utility>

 #include <algorithm>

 #include <vector>

 #include <map>

 // #include<malloc.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define LL long long

 const int inf = 0x3f3f3f3f;

 const double eps = 1e-;

 const double pi = acos(-);

 const LL MOD = 1e9+;

 // const LL p = 1e9+7;

 // inline int r(){

 //     int x=0,f=1;char ch=getchar();

 //     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}

 //     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

 //     return x*f;

 // }

 map<string,int> stu;

 map<string,set<int> > pro;

 vector<pair<int,string> > ans;

 int a[],n,m;

 string str,book;

 void init(){

     stu.clear();

     pro.clear();

     ans.clear();

     clc(a,);

     n=m=;

 }

 bool cmp(const pair<int,string> &a,const pair<int,string> &b){

    if(a.first==b.first) return a.second<b.second;

    return a.first>b.first;

 }

 void work(){

    std::map<string,set<int> >::iterator it;

    std::set<int>::iterator q;

    for(it=pro.begin();it!=pro.end();it++){

       int cnt=;

       for(q=it->second.begin();q!=it->second.end();q++){

          if(a[*q]==) cnt++;

       }

       ans.push_back(make_pair(cnt,it->first));

    }

    sort(ans.begin(),ans.end(),cmp);

    std::vector<pair<int,string> >::iterator p;

    for(p=ans.begin();p!=ans.end();p++){

       cout<<p->second<<" "<<p->first<<endl;

    }

 }

 int main(){

     // freopen("in.txt","r",stdin);

     init();

     while(getline(cin,str)){

        if(str[]=='') break;

        else if(str[]=='') {

           work();

           init();

           continue;

        }

        else{

           if(str[]>='A'&&str[]<='Z'){

              book=str;

              pro[book].insert(-);

           }

           else{

              std::map<string,int>::iterator it = stu.find(str);

              if(it==stu.end())

                 stu[str]=m++;

              std::set<int>::iterator q=pro[book].find(stu[str]);

              if(q==pro[book].end()){

                  a[stu[str]]++;

                  pro[book].insert(stu[str]);

              }

           }

        }

     }

     return ;

 }