首页 > 代码库 > Gym 100971B Derangement

Gym 100971B Derangement

2024-08-11 03:32:43   210人阅读

要求改换序列，使得没有位置是a[i] == i成立。输出最小要换的步数

首先把a[i] == i的位置记录起来，然后两两互相换就可以了。

对于是奇数的情况，和它前一个换或者后一个换就可以，（注意前一个越界或者后一个越界）

这样是不会重复的，因为本来i是a[i] == i的话，换了一个，是不会使得他们两个a[i] == i的

技术分享
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 200000 + 20;int a[maxn];vector<int>pos;void work (){    int n;    cin>>n;    for (int i = 1; i <= n; ++i) scanf ("%d",&a[i]);    for (int i = 1; i <= n; ++i) {        if (a[i] == i)            pos.push_back(i);    }    printf ("%d\n",pos.size() / 2 + (pos.size() & 1));    if (pos.size() & 1) {        for (int i = 0; i < pos.size() - 1; i += 2) {            printf ("%d %d\n",pos[i],pos[i + 1]);        }        int t1 = pos[pos.size() - 1] - 1;        int t2 = pos[pos.size() - 1] + 1;        int ans;        if (t1 != 0) {            ans = t1;        } else {            ans = t2;        }        printf ("%d %d\n",pos[pos.size() - 1],ans);    } else {        for (int i = 0; i < pos.size(); i += 2) {            printf ("%d %d\n",pos[i],pos[i + 1]);        }    }    return ;}int main(){#ifdef local    freopen("data.txt","r",stdin);#endif    work ();    return 0;}
View Code

 

Gym 100971B Derangement


联系
我们