本文主要是介绍Codefoces 432C Prime Swaps(数论+贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：Codefoces 432C Prime Swaps
题目大意：给出一个序列，长度为n，要求用5n以内的交换次数使得序列有序，并且交换的i，j两个位置的数时要满足，j−i+1为素数。
解题思路：a数组为对应的序列，b数组为对应的有序序列，p为对应数的位置。每次从有序序列最小的位置开始，该为必须放b[i]才对，所以p[b[i]]=i,否则就要将b[i]尽量往前换，直到换到i的位置为止。
哥德巴赫猜想：任何一个大于5的数都可以写成三个质数之和。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1e5+5;int n, a[N], b[N], p[N], v[N], r[5*N][2];void init () {memset(v, 0, sizeof(v));for (int i = 2; i <= n; i++) {if (v[i])continue;for (int j = i * 2; j <= n; j += i)v[j] = 1;}for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);b[i] = a[i];p[a[i]] = i;}sort(b+1, b+n+1);
}int solve () {int c = 0;for (int i = 1; i <= n; i++) {while (p[b[i]] != i) {for (int j = i; j < p[b[i]]; j++) {if (!v[p[b[i]] - j + 1]) {r[c][1] = p[b[i]];r[c++][0] = j;int t = p[b[i]];p[b[i]] = j;p[a[j]] = t;swap(a[j], a[t]);break;}}}}return c;
}int main () {scanf("%d", &n);init();int c = solve();printf("%d\n", c);for (int i = 0; i < c; i++)printf("%d %d\n", r[i][0], r[i][1]);return 0;
}这篇关于Codefoces 432C Prime Swaps(数论+贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
