Foreign Exchange(UVA 10763)
网址如下:
Foreign Exchange - UVA 10763 - Virtual Judge (vjudge.net)
(第三方网站)
奇怪,很是奇怪
你可以看看题目的描述:
The program works out only if every student has a suitable exchange partner. In other words, if a student wants to go from A to B, there must be another student who wants to go from B to A.
这很明显表示的是必须每个人两两配对,而间接的交换是不行的:
1 到 2,2 到 3,3 到 1
但是这个网站的测试点是间接的方式也可以(我不是在UVA那刷题的,因为要翻墙)
最后是两个配对方式的都写了一遍
不能间接的代码如下:
#include<cstdio>
#include<map>
using namespace std;
struct exc{int A, B;bool operator<(const exc &tmp) const{return (A < tmp.A) ? true : ((A == tmp.A) ? B < tmp.B : false);}
};
void studInsert(const exc &m);
map<exc, int> students;int main(void)
{int n;while(scanf("%d", &n) == 1 && n){students.clear();for(int i = 0; i < n; i++){exc m;scanf("%d%d", &m.A, &m.B);studInsert(m);}if(students.empty()) printf("YES\n");else printf("NO\n");}return 0;
}
void studInsert(const exc &m)
{exc target{m.B, m.A};auto it = students.find(target);if(it != students.end() && --(it->second) == 0)students.erase(it);else{it = students.find(m);if(it != students.end()) (it->second)++;else students[m] = 1;}
}
可以不用像我用struct,直接用pair就可以了
能间接的代码如下:
#include<cstdio>
#include<cstring>
const int MAXNUM = 100000;
int location[MAXNUM];int main(void)
{int n;while(scanf("%d", &n) == 1 && n){memset(location, 0, sizeof(location));for(int i = 0; i < n; i++){int a, b;scanf("%d%d", &a, &b);location[a]--, location[b]++;}bool isJudege = true;for(int i = 0; i < MAXNUM; i++)if(location[i]){isJudege = false; printf("NO\n"); break;}if(isJudege) printf("YES\n");}return 0;
}
直接哈希表了