Foreign Exchange [UVA - 10763]
程序员文章站
2022-04-17 21:59:43
...
思路:能否成功取决于A->B的数量是否等于B->A的数量,那么只需要想办法判断每对 (A, B) 是否满足。
解决:
(1) 先确定每对 (A, B) 的表达形式。方法很多,我这里是存储每对 (A, B) 时,使 A, B 大小有序,则每一对 A, B 都变成了唯一形式, 可用结构体储存,按规则排序之后 (A, B) 就会相连,这样就便于处理 每一对(A, B) 是否满足。
(2) 确定每一对 (A, B) 是否满足。 给每个学生一个 val 值, 然后 使得A->B 与 B->A 的 val 值相反即可, (A, B) 的 所有val 值 加起来,等于0说明 (A, B) 这一对满足,否则整个情况就不满足。
整个算法复杂度O(n logn)
代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
//#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <set>
using namespace std;
//using namespace __gnu_cxx;
#define pair(a, b) make_pair(a, b)
#define memset(a, b) memset(a, b, sizeof a)
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define fi first
#define se second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 5e5 + 10;
const int M = 2e5 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
const double D = 1e-8;
const double PI = acos(-1.0);
struct Node
{
LL a, b;
int val;
bool operator < (const Node &W) const
{
if (a != W.a) return a < W.a;
return b < W.b;
}
bool operator != (const Node &W) const
{
return a != W.a || b != W.b;
}
} g[N];
int n, m, k;
int main()
{
//freopen("C:\\Users\\86187\\Desktop\\stdin.txt", "r", stdin);
while (cin >> n, n)
{
for (int i = 1; i <= n; i ++)
{
LL a, b;
cin >> a >> b;
int val = (a < b ? 1 : -1);
if (a > b) swap(a, b);
g[i] = {a, b, val};
}
sort(g + 1, g + 1 + n);
int sum = 0;
bool flag = true;
for (int i = 1; i <= n; i ++)
{
if (i == 1 || g[i] != g[i - 1])
{
if (sum) break;
}
sum += g[i].val;
}
if (sum) flag = false;
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}