11292: 【原1292】easy

题目

题目描述

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

Description

简单的题不一定有简单的数据。有n个位置和n个数，初始时每个位置上都放有一个数。我们可以不断的交换两个不同位置上的数，直到达到终止状态。

终止状态指：每个位置上的数都和位置一样，即i号位上的数是i。

同时我们假设进行一次交换用的时间为1，每个单位时间可以对任意对数进行交换操作，但不能对一个数进行两次交换。例如在1的时间里，我们可以交换1跟2、3跟4、5跟6⋯⋯ 但不能交换1跟2、2跟3

求：

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

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

Input Format

每个测试点由10组以内数据组成，每组数据由两行组成

第一行：一个整数n,n<=1000000

第二行：n个整数，第i个整数a[i]表示第i个位置上的数是a[i] 1<=a[i]<=n

Output Format

对于每组数据输出两行，每行一个整数。分别是问题1和2的答案

Sample Input

Sample Output

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 read(){
    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)
        a[i] = read();
    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;
}