2014
01-26

# Another Easy Problem

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.

Can you solve this easy problem?

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.

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.

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

Case 1: 3
Case 2: 0

tag ：模拟

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct stu
{
string id;
set<long long>time;
set<long long>course;
}st[25];
struct cour
{
long long id;
long long cap;
int num;
set<long long>time;
long long no;
}co[25];
struct req
{
string student;
long long id;
long long no;
long long cno;
}re[410];
int n,m,r;
long long x;
bool cmp(req a,req b)
{
if(a.cno==b.cno)
return a.no<b.no;
return a.cno<b.cno;
}
int main()
{
int cas=0;
while(cin>>n>>m>>r)
{
for(int i=0;i<n;i++)
{
cin>>st[i].id;
st[i].course.clear();
st[i].time.clear();
}
for(int i=0;i<m;i++)
{
co[i].no=i;
co[i].time.clear();
cin>>co[i].id>>co[i].cap>>co[i].num;
for(int j=0;j<co[i].num;j++)
{
cin>>x;
co[i].time.insert(x);
}
}
int ans=0;
for(int i=0;i<r;i++)
{
string s;
long long c;
cin>>s>>c;
re[i].student=s;
re[i].id=c;
int y=-1;
for(int i=0;i<m;i++)
{
if(co[i].id==c)
{
y=i;
break;
}
}
re[i].no=i;
re[i].cno=co[y].no;
}
sort(re,re+r,cmp);
for(int cas=0;cas<r;cas++)
{
string s=re[cas].student;
long long c=re[cas].id;
int x=-1,y=-1;
for(int i=0;i<n;i++)
{
if(st[i].id==s)
{
x=i;
break;
}
}
for(int i=0;i<m;i++)
{
if(co[i].id==c)
{
y=i;
break;
}
}
if(x==-1 || y==-1 || co[y].cap<=0)
continue;
bool ok=true;
if(st[x].course.count(c)) //选过了
continue;
for(set<long long>::iterator ii=st[x].time.begin();ii!=st[x].time.end();ii++)
{
if(ok==false)
break;
for(set<long long>::iterator it=co[y].time.begin();it!=co[y].time.end();it++)
{
if(*ii == *it)
{
ok=false;
break;
}
}
}
if(ok==false)
continue;

st[x].course.insert(c);
for(set<long long>::iterator it=co[y].time.begin();it!=co[y].time.end();it++)
st[x].time.insert(*it);
co[y].cap--;
ans++;
}
/*for(set<long long>::iterator ii=st[1].time.begin();ii!=st[1].time.end();ii++)
cout<<*ii<<" ";
cout<<endl;*/
printf("Case %d: %d\n",++cas,ans);
}
return 0;
}

1. [email protected]

2. 这个方法是错的，不信你试试：
20 5
1 A:9
1 A:9
1 A:9
1 A:6
1 A:4
正确答案应该是19，这个答案是18

3. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.