哈希表 + 模拟

受到题目41. 缺失的第一个正数的启发：

因为最终一定是第i个位置要是i。所以我们不妨从左往右扫描。遇到第一个不是$i$的，我们就和当前$i$所在的位置进行交换。

而找到$i$所在的位置就是使用哈希表来记录每个元素所在的下标。然后模拟交换即可

python

n = int(input())
a = list(map(int, input().split()))
s = input()
mp = {} # 记录每个数的位置
c = {} # 记录每个数的颜色
for i in range(n):
    mp[a[i]] = i
    c[a[i]] = s[i]
ok = True 
res = 0
for i in range(n): # 从1开始
    if a[i] == i + 1: # 位置正确
        continue
    pos = mp[i + 1] # 求要swap的位置
    # 如果两个位置的颜色是W，无法swap
    if c[i + 1] == 'W' or c[a[i]] == 'W':
        ok = False
        break
    # swap , 答案 + 1
    res += 1
    mp[a[i]] = pos
    mp[a[pos]] = i 
    a[i], a[pos] = a[pos], a[i]
if ok:
    print(res)
else:
    print(-1)

java

import java.io.*;
import java.util.*;

public class Main {


    static Kattio sc = new Kattio();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public static void main(String[] args) {
//        int t = sc.nextInt();
        int t = 1;
        while (t-- > 0) {
            solve();
        }
        out.flush();
        out.close();
    }

    static long[] inv;
    static List<Integer>[] graph;
    static int[] h;
    static int[] f;
    static int[][] pa;
    static long[][] pb;

    public static void solve() {
        int n = sc.nextInt();
        inv = new long[n];
        graph = new List[n];
        h = new int[n];
        f = new int[n];
        pa = new int[n][18];
        pb = new long[n][18];
        for (int i = 1; i < n; i++) {
            inv[i] = inv(i);
        }
        inv[0] = 1;
        Arrays.setAll(graph, v -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
            graph[u].add(v);
            graph[v].add(u);
        }
        f[0] = -1;
        dfs(0);
        for (int i = 0; i < n; i++) {
            pa[i][0] = f[i];
            pb[i][0] = inv[graph[i].size() - 1];
        }
        for (int j = 0; j < 17; j++) {
            for (int i = 0; i < n; i++) {
                if (pa[i][j] != -1) {
                    pa[i][j + 1] = pa[pa[i][j]][j];
                    pb[i][j + 1] = pb[i][j] * pb[pa[i][j]][j] % MOD;
                }
            }
        }
        int q = sc.nextInt();
        while (q-- > 0) {
            int s = sc.nextInt() - 1, t = sc.nextInt() - 1;
            if (s == t) {
                out.println(1);
                continue;
            }
            int lca = lca(s, t);
            long res = inv[graph[s].size()];
            s = f[s];
            int d = s == -1 ? -1 : h[s] - h[lca] + (t == lca ? 0 : 1);
            if (d > 0) {
                for (int i = 17; i >= 0; i--) {
                    if ((d >> i & 1) != 0) {
                        res = res * pb[s][i] % MOD;
                        s = pa[s][i];
                    }
                }
            }
            t = f[t];
            d = t == -1 ? -1 : h[t] - h[lca];
            if (d > 0) {
                for (int i = 17; i >= 0; i--) {
                    if ((d >> i & 1) != 0) {
                        res = res * pb[t][i] % MOD;
                        t = pa[t][i];
                    }
                }
            }
            out.println(res);
        }
    }

    public static int lca(int x, int y) {
        int min = Math.min(h[x], h[y]);
        if (h[x] == min) {
            y = jump(y, h[y] - min);
        } else {
            x = jump(x, h[x] - min);
        }
        for (int i = 17; i >= 0; i--) {
            if (pa[x][i] != pa[y][i]) {
                x = pa[x][i];
                y = pa[y][i];
            }
        }
        return x == y ? x : f[x];
    }

    public static int jump(int cur, int d) {
        for (int i = 0; i <= 17; i++) {
            if (cur < 0) {
                break;
            }
            if ((d >> i & 1) != 0) {
                cur = pa[cur][i];
            }
        }
        return cur;
    }


    public static void dfs(int cur) {
        for (int next : graph[cur]) {
            if (f[cur] == next) {
                continue;
            }
            h[next] = h[cur] + 1;
            f[next] = cur;
            dfs(next);
        }
    }


//    static final long MAX = (long) 2e18;
//    static final long MIN = -(long) 2e18;

    static final int MAX = 0x3fffffff;
    static final int MIN = -0x3fffffff;

    static final int MOD = 1000000007;


    public static long gcd(long a, long b) {
        return a % b == 0 ? b : gcd(b, a % b);
    }

    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    public static long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) != 0) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    public static long inv(long a) {
        return pow(a, MOD - 2);
    }

    public static boolean linearEquation(long[] ans, long a, long b, long m) {
        long d = ext_gcd(ans, a, b);
        if (m % d != 0) {
            return false;
        }
        long n = m / d;
        ans[0] *= n;
        ans[1] *= n;
        return true;
    }

    public static long ext_gcd(long[] ans, long a, long b) {
        if (b == 0) {
            ans[0] = 1;
            ans[1] = 0;
            return a;
        }
        long res = ext_gcd(ans, b, a % b);
        long tmp = ans[0];
        ans[0] = ans[1];
        ans[1] = tmp - a / b * ans[1];
        return res;
    }

    public static int[] getZ(char[] str) {
        int N = str.length;
        int[] z = new int[N];
        z[0] = N;
        for (int i = 1, l = 0, r = 0; i < N; i++) {
            z[i] = Math.max(Math.min(z[i - l], r - i + 1), 0);
            while (i + z[i] < N && str[z[i]] == str[i + z[i]]) {
                l = i;
                r = i + z[i];
                z[i]++;
            }
        }
        return z;
    }

    static class Kattio extends PrintWriter {
        static BufferedReader r;
        static StringTokenizer st;

        public Kattio() {
            this(System.in, System.out);
        }

        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }

        public Kattio(String input, String out) throws IOException {
            super(out);
            r = new BufferedReader(new FileReader(input));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(r.readLine());
                }
                return st.nextToken();
            } catch (Exception e) {
                // TODO: handle exception
                return null;
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int>m,m2;
    int a;
    for(int i = 1;i<=n;i++)
    {
        cin>>a;
        m[i] = a;
    }
    for(int i = 1;i<=n;i++)
    {
        m2[m[i]] = i;
    }
    string str;
    cin>>str;
    int cnt = 0;
    int k = 0;
    
    for(int i = 1;i<=n;i++)
    {
        //cout<<-1<<" "<<m[i]<<endl;
        if(m[i] == i) continue;
        if(str[i-1] == 'W' || str[m2[i]-1] == 'W')
        {
            cout<<-1;
            return 0;
        }
        else {
            k = m[i];
            //m[i] = i;
            m[m2[i]] = k;
            m2[k] = m2[i];
        

        m2[i] = 
        //cout<<-2<<" "<<m[i]<<" "<<m2[i]<<endl;
        cnt++;
        }
        
    }
    cout<<cnt;
    return 0;
}

题目描述

小美有一个排列，所有元素为红色或者白色。

小美可以交换任意两个红色元素的位置，并希望用最少次数使得数组变为非降序。最少要用多少次？

输入描述

第一行一个正整数$n(n\le10^5)$，表示数组的长度

第二行$n$个正整数$a_i$

第三行为一个长为$n$的字符串，表示染色情况，$R$为红色，$W$为白色。

输出描述

一个整数，表示答案。

如果无法完成，则输出-1。

样例

输入

4
1 3 2 4
WRRW

输出

1