首页 > 代码库 > Codeforces 489A SwapSort
Codeforces 489A SwapSort
这题第一次看的时候以为是区间替换,后来发现看错了,只是单纯的元素替换。
解题思路:
先对输入的序列加个数组排个序
遍历下来,如果和排序后的结果当前元素不同,设当前位置为 i, 则往下面找,设查找位置为j
使得满足 a[j] == b[i] && a[j] != b[j]
一次遍历即可。易得证
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;int a[3111], b[3111], n, counti;int ans[3111][2];int main(){ int i, j, t, m; while(EOF != scanf("%d",&n)){ counti = 0; for(i = 1; i <= n; ++i){ scanf("%d",&a[i]); b[i] = a[i]; } sort(b + 1, b + 1 + n); for(i = 1; i <= n; ++i){ if(a[i] != b[i]){ for(j = i + 1; j <= n; ++j){ if(a[j] == b[i] && a[j] != b[j]){ swap(a[j], a[i]); ++counti; ans[counti][0] = j; ans[counti][1] = i; break; } } } } printf("%d\n",counti); for(i = 1; i <= counti; ++i){ printf("%d %d\n",ans[i][1] - 1, ans[i][0] - 1); } } return 0;}
Codeforces 489A SwapSort
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。