Description
You have an array a[1],?a[2],?...,?a[n], containing distinct integers from 1 to n. Your task is to sort this array in increasing order with the following operation (you may need to apply it multiple times):
You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5n operations.
Input
The first line contains integer n(1?≤?n?≤?105). The next line contains n distinct integers a[1],?a[2],?...,?a[n](1?≤?a[i]?≤?n).
Output
In the first line, print integer k(0?≤?k?≤?5n) — the number of used operations. Next, print the operations. Each operation must be printed as "ij" (1?≤?i?<?j?≤?n; (j?-?i?+?1) is a prime).
If there are multiple answers, you can print any of them.
Sample Input
3
3 2 1
1
1 3
2
1 2
0
4
4 2 3 1
3
2 4
1 2
2 4
看到这个题，好像没有什么思路，但是一旦模拟一下几组数据，就发现，不难，由于每个数都是n之类的数，而且都不相同，简单的循环一次，把每个数放在它应该放得位置，这样最终的次数就不会超过5n，为什么呢，我也不知道为什么啊，这个方法虽然想到了，可是自己也不知道，看别人的也是这样做，这个题还有一点就是，判断是否是prime时，不要每次都去判断，把500000以内的prime数记录一下，这样时间会得到很大的优化
#include<map> #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x0f0f0f0f using namespace std; const int maxn=100000+10; bool vis[maxn]; void prime() { memset(vis,0,sizeof(vis)); vis[1]=1; //c=0; for (long long i=2;i<=100000;i++) { if (!vis[i]) { //prm[c++]=i; //cout<<i<<" "; if (i*i<100000){ for (long long j=i*i;j<=100000;j+=i) vis[j]=1;} } } } int main() { prime(); int n,a[maxn],id[maxn]; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); id[a[i]]=i; } int x[maxn*5],y[maxn*5]; int cut=0; for (int i=1;i<=n;i++) { while (id[i]!=i) { int j=i; while(vis[id[i]-j+1]!=0) j++; x[cut]=j; y[cut]=id[i]; a[id[i]]=a[j]; id[a[j]]=id[i]; a[j]=i; id[i]=j; cut++; } } printf("%d\n",cut); for (int i=0;i<cut;i++) printf("%d %d\n",x[i],y[i]); return 0; }
作者 chensunrise
CodeForces 432C Prime Swaps,布布扣,bubuko.com
原文：http://www.cnblogs.com/chensunrise/p/3761820.html