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

时间:2021-01-11 15:04:42

题意:有若干交换生、若干学校,有人希望从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][b], --all[b][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[b];
}
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有这么慢?好吧。