C. Prime Swaps（暴力+贪心）

亦凉 2021-11-05 13:00 244阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/432/C][http_codeforces.com_problemset_problem_432_C]

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):

choose two indexes, i and j (1 ≤ i < j ≤ n; (j - i + 1) is a prime number);  
swap the elements on positions i and j; in other words, you are allowed to apply the following sequence of assignments: tmp = a\[i\], a\[i\] = a\[j\], a\[j\] = tmp (tmp is a temporary variable).

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 “i j” (1 ≤ i < j ≤ n; (j - i + 1) is a prime).

If there are multiple answers, you can print any of them.  
Examples  
Input  
Copy

3  
3 2 1

Output  
Copy

1  
1 3

Input  
Copy

2  
1 2

Output  
Copy

Input  
Copy

4  
4 2 3 1

Output  
Copy

3  
2 4  
1 2  
2 4

分析：  
这个题一开始的思路，是用两个map映射。分别映射val值得pos值。pos值得val值但是处理起来较为麻烦。  
这个题从第一个位置开始考虑。  
我们先找到1这个数的位置，通过不断地交换，把他换到第一个位置来。在这个交换过程中，我们应该不断地找到不大于pos\[val\] - i+ 1的最大素数。  
从而把二者（pos\[val\]，pos\[val\]-i+1）位置的值交换。  
不断反复如此，可达到目的。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    typedef pair<int,int> PII;
    int n,a[100100],pos[100100];
    int prime[100101],top;
    int vis[1000101];
    int max_prime;
    vector<PII> Q;
    
    void init()
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d",&a[i]);
            pos[a[i]] = i;
        }
    
        for(int i = 2; i <= n; i ++)
        {
            if(vis[i] == 0)
                prime[++ top] = i;
            else
                continue;
            for(int j = i * 2; j <= n; j += i)
                vis[j] = 1;
        }
    }
    
    void sum_prime(int dis)
    {
        for(int i = top; i >= 1; i --)
        {
           // printf("prime = %d\n",prime[i]);
            if(prime[i] <= dis)
            {
                max_prime = prime[i]; return ;
            }
        }
    }
    
    void do_swap(int i,int j)
    {
        int x = a[i],y = a[j];
        swap(a[i],a[j]);
        swap(pos[x],pos[y]);
        Q.push_back({j,i});
    }
    
    int main()
    {
        init();
        for(int i = 1; i <= n; i ++)
        {
            while(pos[i] != i)
            {
                int ans = pos[i] - i + 1;
                sum_prime(ans);
                //printf("ans = %d max_prime = %d\n",ans,max_prime);
                do_swap(pos[i],pos[i] - max_prime + 1);
            }
        }
        printf("%d\n",Q.size());
        for(int i = 0; i < Q.size(); i ++)
            printf("%d %d\n",Q[i].first,Q[i].second);
    }

[http_codeforces.com_problemset_problem_432_C]: http://codeforces.com/problemset/problem/432/C