[PAT解题报告] Student List for Course
简直是1039的副本。反过来问，求每门课程都有哪些人选？我仍然采取和1039同样的方法，(课程编号 << 16) |
人编号，
这个整数作为一条边。因为人不超过40000个，所以用低16bit没有任何问题。并且我存了一个人编号到姓名的映射——就是一个简单数组，name[i]表示编号为i的那个人的名字。所以，这样就没有1039把字符串变为int的问题了。重点还是二分查找。
代码：
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>
using namespace std;
int all[800002];
int total;
char name[40002][5];
int find1(int x) { // first >= x
int left = 0, right = total - 1, r = -1;
while (left <= right) {
int mid = (left + right) >> 1;
if (all[mid] >= x) {
r = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return r;
}
int find2(int left,int x) { //last <= x
int right = total - 1;
++left;
while (left <= right) {
int mid = (left + right) >> 1;
if (all[mid] <= x) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left - 1;
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0;i < n;++i) {
int y;
scanf("%s%d",name[i],&y);
for (;y;--y) {
int z;
scanf("%d",&z);
all[total++] = (z << 16) | i;
}
}
sort(all, all + total);
for (int i = 1; i <= m; ++i) {
printf("%d",i);
int y = find1(i << 16);
if ((y < 0) || ((all[y] >> 16) > i)) {
puts(" 0");
}
else {
int x = find2(y, (i << 16) | (n - 1));
printf(" %d\n",x - y + 1);
vector<string> temp;
for (; y <= x; ++y) {
temp.push_back(name[all[y] & 65535]);
}
sort(temp.begin(), temp.end());
for (int j = 0; j < temp.size(); ++j) {
puts(temp[j].c_str());
}
}
}
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1047
