2472: fzx的交换
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
fzx 有一个长度为 n 的初始 (ai = i, 1 ≤ i ≤ n) 的数组,和长度为 m 的交换序列,他会按照序列顺序每次交换 2 个数
你需要准确地删除恰好一个交换操作,使得数字 1 最后交换到第 k 个位置,并输出需要删掉的交换操作的序号
如果有多个答案，输出序号最小的交换操作的序号
保证有解
输入
第一行 3 个正整数 n,m,k ,表示 n 个数, m 个交换，最终希望数字 1 交换到第 k 个位置
接下来 m 行每行 2 个数 a,b ,表示交换 a,b 位置上的数字
输出
输出一个数表示序号最小的交换操作的序号，删掉这个序号后数字 1 可以交换到位置 k
样例输入 复制
样例一：
10 10 9
1 8
8 3
3 4
4 7
7 2
6 2
9 10
3 10
9 3
6 9
样例二：
10 10 2
1 3
3 4
4 1
1 5
3 7
7 9
3 6
4 3
10 8
5 2样例输出 复制
样例一：
7
样例二：
5提示
对于 4040 %的数据 n,m \leq 1000n,m≤1000
对于另外 3030 %的数据 保证不删除操作前经过m个操作,数字 11 恰好交换到第 kk 个位置
对于 100100 %的数据,n,m \leq 100000n,m≤100000
#include <stdio.h>
#include <iostream>
#define N 100005
using namespace std;
int n, m, k, ans, a[N], b[N], p[N], q[N];
int main() {
//freopen("swap.in", "r", stdin);
//freopen("swap.out", "w", stdout);
int i, j;
scanf("%d%d%d", &n, &m, &k);
for(i = 1; i <= m; i++)
scanf("%d%d", &a[i], &b[i]);
p[0] = 1;
for(i = 1; i <= m; i++) {
p[i] = p[i-1];
if(p[i] == a[i]) p[i] = b[i];
else if(p[i] == b[i]) p[i] = a[i];
}
for(i = 1; i <= n; i++)
q[i] = i;
for(i = m; i; --i) {
if(q[p[i-1]] == k) ans = i;
swap(q[a[i]], q[b[i]]);
}
printf("%d\n", ans);
return 0;
}