欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}
相关标签: 蓝书

上一篇: 我没带书

下一篇: 比他爸会挑男人