[刷题]算法竞赛入门经典(第2版) 5-4/UVa10763

pennate

　　题意：有若干交换生、若干学校，有人希望从A校到B校，有的想从B到C、C到A等等等等。如果有人想从A到B也刚好有人想从B到A，那么可以交换（不允许一对多、多对一）。看作后如果有人找不到人交换，那么整个交换计划失败。
　　代码：（Accepted， 50ms）

//UVa10763 - Foreign Exchange
#include<cstdio>
#include<cstring>
int N, a, b,all[1003][1003];
int main() {
//freopen("in.txt", "r", stdin);
while (scanf("%d", &N) != -1 && N != 0) {
memset(all, 0, sizeof(all));
while (N--) {
scanf("%d%d", &a, &b);
++all[a], --all[a];
}
int *p = all[0], i = 0;
for (;i < 1006009;++i, ++p)
if (*p != 0) break;
printf(i<1006009 ? "NO\n" : "YES\n");
}
return 0;
}
　　分析：一开始我使用multimap < int,int >去完全的模拟，但是其实我不大会使用，不知道怎么删除单个元素而不把整个key删除，就把那个元素置为-1。最后遍历一遍看看有没有不是-1的。结果。。。。虽然一遍过了，蛮开心，但一看结果1870ms！！！我的天呐！我开始怀疑人生啦！近2000毫秒什么鬼！突然怀疑我是不是不适合计算机这个专业/(ㄒoㄒ)/~~。于是去网上看他们怎么做的。好吧，好好一个题目被我搞复杂了。神经病啦，谁需要用到multimap啦。

看到网上有几个方法：
1. 就是我现在的方法，定义一个二维数组all，all[A][B]即为A到B的人数。下标1000就够了，题目的数据里没有标号更大的学校（但1000*1000还是好大！又是空间换时间的交♂易，不过这场交♂易明显合算啊）。
2. 把“原来所在学校x”到“交换目标学校y”的数据输入数组后，排序；再按照y到x的顺序存入数组，排序；若两个数组一样，则yes。相当好的想法呢。就是实现烦一点而且有bug（待会说）。
3. 直接统计各个学校想进来、想出去的人数，看看是不是平衡。与方法2有一样的bug。
　　好，说说那个bug。就是甲：A→B；乙：B→C；丙：C→A；的情况。题目只说了A到B、B到A可行，没说这个也行。但是VJ和博客上看到好多这两个方法的也AC了，而且代码又快又少。一开始有点懵圈了，不知道是题目没说清还是代码的bug。现在想想应该是网友没想到这点吧。但是我还是用法三做了一遍：（法三，Accepted， 60ms）

//UVa10763 - Foreign Exchange
#include<iostream>
#include<map>
int N, a, b;
int main()
{
//freopen("in.txt", "r", stdin);
while (scanf("%d", &N) != -1 && N != 0) {
std::map<int, int> all;
while (N--) {
scanf("%d%d", &a, &b);
++all[a], --all;
}
bool num = false;
for (const auto &r : all)
if (r.second) { num = true;break; }
printf(num ? "NO\n" : "YES\n");
}
return 0;
}
　　出人意料的那个用all[1003][1003]的方法比法三那个投机取巧还便宜了10ms。map有这么慢？好吧。