首页 > 代码库 > CodeForces 489A (瞎搞) SwapSort

CodeForces 489A (瞎搞) SwapSort

2024-08-02 21:46:05   219人阅读

题意：

给n个整数(可能有重复)，输出一个不超过n次交换的方案，使得经过这n次交换后，整个序列正好是非递减的。

分析：

首先说题解给的算法。

从左到右扫一遍，交换第i个数和它后面最小的那个数。

代码看起来大概是这个样子的：

 1     for (int i = 0; i < n; i++) 2     { 3         int j = i; 4         for (int t = i; t < n; t++) 5             if (a[j] > a[t]) 6                 j = t; 7         if (i != j) 8             answer.push_back(make_pair(i, j)); 9         swap(a[i], a[j]);10     }
代码君

 

当时看到这题一直没有明确的思路，于是开始乱搞。 =_=||

首先排了下序，然后从左到右逐个对比原序列和排序后的序列，如果有不一样的，就从原序列的后面把这个“正确”的数找出来交换，直到两个序列完全相同。

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 3000 + 10; 8 int a[maxn], b[maxn], ans[maxn][2]; 9 10 int main()11 {12     int n;13     while(scanf("%d", &n) == 1 && n){14     for(int i = 0; i < n; ++i)15     {16         scanf("%d", &a[i]);17         b[i] = a[i];18     }19     sort(b, b + n);20 21     int cnt = 0;22     bool flag;        //标记是否发生过交换23     while(1)24     {25         flag = false;26         for(int i = 0; i < n; ++i)27         {28             if(a[i] != b[i])29             {30                 flag = true;31                 for(int j = n-1; j >= 0; --j)32                     if(a[j] == b[i] && i != j)33                     {34                         swap(a[i], a[j]);35                         ans[cnt][0] = i;36                         ans[cnt++][1] = j;37                         break;38                     }39             }40         }41         if(!flag)   break;42     }43     printf("%d\n", cnt);44     for(int i = 0; i < cnt; ++i) printf("%d %d\n", ans[i][0], ans[i][1]);45     }46 47     return 0;48 }
代码君

 

CodeForces 489A (瞎搞) SwapSort


联系
我们