Another Easy Problem
http://acm.hdu.edu.cn/showproblem.php?pid=2418
Problem Description
Nowadays, many universities no longer force students to follow a fixed curriculum; instead they allow students to choose the courses on an individual basis. However, new programs need to be written to satisfy such needs. Your job is to write such a program.
In our system, the following objects exist: Time Period, Course and Student. The relationships between the three objects are as follows:
A course has a capacity, and is associated with multiple time periods; a student can register for multiple courses in the system (resulting in a possibly conflicting schedule).
To resolve possible conflicts with the schedules as well as to ensure that the number of students registered for each course does not exceed its capacity, the system will use the logic described below to determine the result:
Process courses, in the order they appear in the input.
For each course: Check each student's request in the order it is received, and reject the request if a) accepting the request will result in a conflict in the student's schedule, or b) if no more students could be accepted by this class, or c) the student has
already enrolled in this class; otherwise, the request is accepted.
In our system, the following objects exist: Time Period, Course and Student. The relationships between the three objects are as follows:
A course has a capacity, and is associated with multiple time periods; a student can register for multiple courses in the system (resulting in a possibly conflicting schedule).
To resolve possible conflicts with the schedules as well as to ensure that the number of students registered for each course does not exceed its capacity, the system will use the logic described below to determine the result:
Process courses, in the order they appear in the input.
For each course: Check each student's request in the order it is received, and reject the request if a) accepting the request will result in a conflict in the student's schedule, or b) if no more students could be accepted by this class, or c) the student has
already enrolled in this class; otherwise, the request is accepted.
Can you solve this easy problem?
Input
There are multiple test cases in the input file.
Each test case starts with three integers, N, M and R (1 <= N <= 20, 1 <= M <= 20, 0 <= R <= N * M), the number of students, the number of courses, and the number of requests, respectively.
Each of the following N lines contains one string, the ID of the student. The ID will contain no characters other than '0'...'9' The next part of each test case consists of M lines, each of which contains three integers, I, C, T, (C <= 100, T <= 30), the ID
of the course, the capacity, and the number of time periods used by the course respectively; T more integers follows, representing the unique identifiers of the time periods. The description for the requests comes next, each line in the format of [Student
ID](Space character)[Course ID], in the order as the requests are received. It is guaranteed that the requests are always valid, i.e., both the student ID and the course ID could be found in the description given above.
Two consecutive test cases are separated by a blank line. Input ends with End-of-File.
Each test case starts with three integers, N, M and R (1 <= N <= 20, 1 <= M <= 20, 0 <= R <= N * M), the number of students, the number of courses, and the number of requests, respectively.
Each of the following N lines contains one string, the ID of the student. The ID will contain no characters other than '0'...'9' The next part of each test case consists of M lines, each of which contains three integers, I, C, T, (C <= 100, T <= 30), the ID
of the course, the capacity, and the number of time periods used by the course respectively; T more integers follows, representing the unique identifiers of the time periods. The description for the requests comes next, each line in the format of [Student
ID](Space character)[Course ID], in the order as the requests are received. It is guaranteed that the requests are always valid, i.e., both the student ID and the course ID could be found in the description given above.
Two consecutive test cases are separated by a blank line. Input ends with End-of-File.
Output
For each test case, print the total number of requests accepted by the system, in the format as indicated in the sample output.
Sample Input
2 2 4 0 1 101 1 2 3 4 102 2 1 5 0 101 1 102 1 101 0 102 1 1 0 4 5 1 1 5
Sample Output
Case 1: 3 Case 2: 0
Source
这题我提交了不下30多次。T-T
首先，这题从技术上来讲没有多大难度，坑就坑在英文题目的理解和题目里的陷阱吧。
题意上就是请求要按照课程在input出现的顺序排序，相同课程的按请求出现的顺序排序。
在不断的WA中，我发现了以下几个可能遇到的陷阱
1：课程可能不占用时间。 比如：课程号 111 时间无。
2：课程的时间会重复出现，比如：课程号 111 时间为 1 2 2 3 4 5.....。
#include<iostream>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
struct ct//课程
{
int cap;//课容量
set<int> cor;//课时间
} temp;
struct st//学生
{
set<int> chosed;//已选课程
set<int> timex;//已占时间
} temt;
struct rt//请求
{
string a;//学生号
int b;//课程号
int ct;//请求次序
} re[515];
map<int,struct ct> course;//课程查找
map<string,struct st> stud;//学生查找
map<int,int> flag;//课程次序
bool cmp(const struct rt &a,const struct rt &b)
{
if(flag[a.b]<flag[b.b]) return true;
else if(flag[a.b]==flag[b.b])
{
return a.ct<b.ct;
}
else return false;
}
int main()
{
int n,m,r,cnt,t,a,cas=0,cname;
string sname;
for(cnt=0; cin>>n>>m>>r; cnt=0)
{
course.clear();
stud.clear();
flag.clear();
temt.chosed.clear();
temt.timex.clear();
for(int i=0; i<n; ++i)
{
cin>>sname;
stud.insert(make_pair(sname,temt));
}
for (int i=0; i<m; ++i)
{
temp.cor.clear();
cin>>cname>>temp.cap>>t;
flag.insert(make_pair(cname,i));
for(int j=0; j<t; ++j)
{
cin>>a;
temp.cor.insert(a);
}
course[cname]=temp;
}
map<int,struct ct>::iterator itc;
map<string,struct st>::iterator its;
for(int i=0; i<r; ++i)
{
cin>>re[i].a>>re[i].b;
re[i].ct=i;
}
sort(re,re+r,cmp);//排序
for(int i=0;i<r;++i)
{
sname=re[i].a;//请求的学生号
cname=re[i].b;//请求的课程号
bool flag=true;
itc=course.find(cname);
its=stud.find(sname);
if(itc->second.cap<=0) continue;//课程容量等于0，不接受请求
if((its->second.chosed.count(cname))!=0) continue;//该学生已选该课程，不接受请求
int len=itc->second.cor.size();
for(set<int>::iterator jt=itc->second.cor.begin();jt!=itc->second.cor.end();++jt)//查看是否有时间冲突
{
if((its->second.timex.count(*jt))!=0)
{
flag=false;
break;
}
}
if(flag)//可以接受改请求
{
cnt++;
(itc->second.cap)--;//该课程容量减少
its->second.chosed.insert(cname);
for(set<int>::iterator jt=itc->second.cor.begin();jt!=itc->second.cor.end();++jt)
its->second.timex.insert(*jt);
}
}
printf("Case %d: %d\n",++cas,cnt);
}
return 0;
}