# 11292: 【原1292】easy

### 题目描述

author: 王立力 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1292

1.到达终止状态最少经过几次交换

2.到达终止状态最少需要的时间

## Sample Input

``````2
2 1
2
2 1
``````

## Sample Output

``````1
1
1
1
``````

## q4x3's solution

``````/**
* 模拟(数学题?)
* 先找环
* 交换次数: 所有环交换次数相加
* 交换时间: 长度为一的环0，长度
* 为二的环1，长度大于等于三的环2
**/
#include <iostream>

using namespace std;

int n, d[1000233], flag[1000233];
int ans1, ans2;

int main() {
while(cin >> n) {
ans1 = 0; ans2 = 0;
for(int i = 1;i <= n;++ i) {
cin >> d[i];
if(d[i] == i) flag[i] = 1;
if(d[i] != i) flag[i] = 0;
}
for(int i = 1;i <= n;++ i) {
if(flag[i]) continue;
int j = d[i], cnt = 0;
while(j != i) {
flag[j] = 1;
j = d[j];
++ cnt;
}
ans1 += cnt;
if(cnt > 1) ans2 = 2;
if(cnt == 1 && ans2 != 2) ans2 = 1;
}
cout << ans1 << endl << ans2 << endl;
}
}
``````

## victrid's solution

``````#include <iostream>
using namespace std;
//Cyka. I'm a blind starcraft player
//I'm a blind starcraft player
//I'm a blind starcraft player
inline int swapi(int& i, int& j) {
int temp = i;
i        = j;
j        = temp;
return 0;
}
int main() {
int numbers;
int maxround[10]   = {0};
int totalsteps[10] = {0};
int groupcount     = 0;
while (~scanf("%d", &numbers)) {
int* ff              = new int[numbers + 1];
maxround[groupcount] = 0;
for (int i = 1; i <= numbers; i++)
cin >> ff[i];
for (int i = 1; i <= numbers; i++) {
if (ff[i] != i) {
int round = 0;
//looping
int tws1 = i, tws2;
while (true) {
for (tws2 = i; ff[tws2] != tws1; tws2++)
;
swap(ff[tws1], ff[tws2]);
totalsteps[groupcount]++;
round++;
if (round > 2)
round = 2;
if (ff[tws2] == tws2) {
maxround[groupcount] = maxround[groupcount] > round ? maxround[groupcount] : round;
break;
}
tws1 = tws2;
}
}
}
groupcount++;
}

for (int i = 0; i < groupcount; i++) {
if (i)
cout << endl;
cout << totalsteps[i] << endl
<< maxround[i];
}
return 0;
}
``````

## zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1292.pdf
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, a[1000005];
bool vis[1000005];
void init(){
for (int i = 1; i <= n; ++i)
memset(vis, 0, sizeof(vis));
}
void solve(){
int tm = 0, maxi = 0;
for (int i = 1; i <= n; ++i){
if (vis[i] || i == a[i]) continue;
int t = a[i], cnt = 1;
vis[i] = true;
while (t != i)
vis[t] = true, t = a[t], ++cnt;
maxi = max(maxi, (cnt == 2 ? 1: 2));
tm += (cnt == 2 ? 1: cnt - 1);
}
printf("%d\n%d\n", tm, maxi);
}
int main(){
while (scanf("%d", &n) == 1){
init();
solve();
}
return 0;
}
``````