题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3862
思路 因为交换次数达到 n + 10
其实我们可以先将他们都重新排序一下 在xoy 坐标系上 从左下角到右上角排序 然后 第2k 和 第 2k+1 之间连一条线
之后只需要交换顺序 来使得原序列变成现在的序列即可
其实在交换的时候 我们就需要交换 新点和旧点
比如这个样例当中
0 0 1 0 1 2 1 1 3 1 0 4
原来的 连接顺序是 1 3 2 4
排序后的连接顺序是 1 2 3 4
所以 我们只需要将 2 3 两个点交换位置即可 这个时候 2 就有 3 那个点所有的状态 3 就有 2 那个点原来的状态 包括 对应关系
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1); const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 2e5 + 5; const int MOD = 1e9 + 7; int f[maxn]; struct Node { int x, y, id; void read() { scanf("%d%d", &x, &y); } }q[maxn]; bool comp(Node x, Node y) { if (x.x == y.x) return x.y < y.y; return x.x < y.x; } int main() { int T; cin >> T; while (T--) { CLR(f); CLR(q); int n; scanf("%d", &n); int m = n << 1; for (int i = 1; i <= m; i++) { q[i].read(); q[i].id = i; } int x, y; for (int i = 0; i < n; i++) { scanf("%d%d", &x, &y); f[x] = y; f[y] = x; } sort(q + 1, q + 1 + m, comp); map <int, int> M; for (int i = 1; i <= m; i++) M[q[i].id] = i; vector <pii> ans; for (int i = 1; i <= m; i += 2) { int a = q[i].id, b = q[i + 1].id; if (f[a] != b) { int c = f[a]; ans.pb(pii(b, c)); swap(q[i + 1].id, q[M[c]].id); swap(M[b], M[c]); } } int len = ans.size(); printf("%d\n", len); vector <pii>::iterator it; if (len) { for (it = ans.begin(); it != ans.end(); it++) printf("%d %d\n", (*it).first, (*it).second); } } }转载于:https://www.cnblogs.com/Dup4/p/9433145.html
