首页 > 代码库 > Gym 100971B Derangement
Gym 100971B Derangement
要求改换序列,使得没有位置是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;}
Gym 100971B Derangement
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。