头像

f@ck1ngCumm1ng

我看我,完全是不懂哦




离线:43分钟前


最近来访(38)
用户头像
Erase_easy
用户头像
OI
用户头像
aaaa不了c
用户头像
AuroraY
用户头像
RyanMoriarty
用户头像
无规则打野你以为
用户头像
科宇
用户头像
静下来操作
用户头像
1s乖ヽ嫁莪
用户头像
白金之星
用户头像
算法小爱
用户头像
雾满杨溪
用户头像
3.1415926535897932384
用户头像
zombotany
用户头像
liuxiaocs
用户头像
夏语聪
用户头像
zmj2008
用户头像
乌搏猿
用户头像
lixiaoqian
用户头像
大菜狗

活动打卡代码 AcWing 789. 数的范围

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        String[] nk = sc.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);
        int[] arr = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        while (k-- > 0) {
            int idx = Integer.valueOf(sc.readLine());
            System.out.println(binarySearch(arr, 0, n - 1, idx, true) + " " + binarySearch(arr, 0, n - 1, idx, false));
        }
    }

    public static int binarySearch(int[] arr, int l, int r, int k, boolean left) {
        while (l <= r) {
            int mid = l + r >> 1;
            if (arr[mid] < k) {
                l = mid + 1;
            } else if (arr[mid] > k) {
                r = mid - 1;
            } else {
                if (left) {
                    if (mid == 0 || arr[mid - 1] != k) {
                        return mid;
                    } else {
                        r = mid - 1;
                    }
                } else {
                    if (mid == arr.length - 1 || arr[mid + 1] != k) {
                        return mid;
                    } else {
                        l = mid + 1;
                    }
                }
            }
        }
        return -1;
    }
}



很多人一开始可能会觉得你都排序了,还怎么算逆序对啊?其实利用归并排序「自底向上」的性质无需担心排好序后会影响结果,因为它是逐层返回的,排好的 2 个子 sub 合并到一个大的父 sub,这个 sub 之间的逆序对已经算完了,他们和「后面位置」的 sub 还是保持着整个的初次的先后顺序,所以我们只要每次计算左边的 sub 和右边的 sub 数组的逆序对就可以了。
利用有序的性质,就可以得到「左边尾部」到「当前位置」的长度(也就是逆序对的个数)。

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

public class Main {

    static int[] cnt;
    static long ans = 0L;
    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        sc.readLine();
        int[] arr = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        cnt = new int[arr.length];
        mergeSort(arr, 0, arr.length);
        System.out.println(ans);
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l >= r - 1) {
            return;
        }
        int m = (l + r) >>> 1;
        mergeSort(arr, l, m);
        mergeSort(arr, m, r);
        int[] tmp = new int[r - l];
        int a = l;
        int b = m;
        for (int i = 0; i < r - l; i++) {
            if (a >= m) {
                tmp[i] = arr[b++];
            } else if (b >= r) {
                tmp[i] = arr[a++];
            } else {
                boolean flag = arr[a] <= arr[b];
                ans += flag ? 0 : m - a;
                tmp[i] = flag ? arr[a++] : arr[b++];
            }
        }
        System.arraycopy(tmp, 0, arr, l, r - l);
    }

}


活动打卡代码 AcWing 788. 逆序对的数量

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

public class Main {

    static int[] cnt;
    static long ans = 0L;
    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        sc.readLine();
        int[] arr = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        cnt = new int[arr.length];
        mergeSort(arr, 0, arr.length);
        System.out.println(ans);
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l >= r - 1) {
            return;
        }
        int m = (l + r) >>> 1;
        mergeSort(arr, l, m);
        mergeSort(arr, m, r);
        int[] tmp = new int[r - l];
        int a = l;
        int b = m;
        for (int i = 0; i < r - l; i++) {
            if (a >= m) {
                tmp[i] = arr[b++];
            } else if (b >= r) {
                tmp[i] = arr[a++];
            } else {
                boolean flag = arr[a] <= arr[b];
                ans += flag ? 0 : m - a;
                tmp[i] = flag ? arr[a++] : arr[b++];
            }
        }
        System.arraycopy(tmp, 0, arr, l, r - l);
    }

}


活动打卡代码 AcWing 787. 归并排序

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        sc.readLine();
        int[] arr = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        mergeSort(arr, 0, arr.length);
        for (int n : arr) {
            System.out.print(n + " ");
        }

    }
    public static void mergeSort(int[] arr, int l, int r) {
        if (l >= r - 1) {
            return;
        }
        int m = (l + r) >>> 1;
        mergeSort(arr, l, m);
        mergeSort(arr, m, r);

        int[] tmp = new int[r - l];
        int left = l;
        int right = m;
        for (int i = 0; i < r - l; i++) {
            if (left >= m) {
                tmp[i] = arr[right++];
                continue;
            }
            if (right >= r) {
                tmp[i] = arr[left++];
                continue;
            }
            if (arr[left] <= arr[right]) {
                tmp[i] = arr[left++];
            } else {
                tmp[i] = arr[right++];
            }
        }
        System.arraycopy(tmp, 0, arr, l, r - l);

    }
}


活动打卡代码 AcWing 786. 第k个数

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

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int[] nk = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] arr = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(fuck(arr, 0, nk[0] - 1, nk[1] - 1));
    }

    public static int fuck(int[] arr, int l, int r, int k) {
        int nxtL = l;
        int nxtR = r;
        int p = l;

        while (l < r) {
            while (l < r) {
                if (arr[r] < arr[p]) {
                    arr[r] ^= arr[p];
                    arr[p] ^= arr[r];
                    arr[r] ^= arr[p];
                    p = r;
                    break;
                }
                r--;
            }
            while (l < r) {
                if (arr[l] > arr[p]) {
                    arr[l] ^= arr[p];
                    arr[p] ^= arr[l];
                    arr[l] ^= arr[p];
                    p = l;
                    break;
                }
                l++;
            }
        }
        if (p == k) {
            return arr[p];
        } else if (p < k) {
            return fuck(arr, p + 1, nxtR, k);
        } else {
            return fuck(arr, nxtL, p - 1, k);
        }
    }
}


活动打卡代码 AcWing 907. 区间覆盖

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

public class Main {

    // System.out.println();
    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        String[] nk = sc.readLine().split(" ");
        int s = Integer.parseInt(nk[0]);
        int t = Integer.parseInt(nk[1]);
        int m = Integer.parseInt(sc.readLine());
        int[][] matrix = new int[m][2];
        for (int i = 0; i < m; i++) {
            matrix[i] = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(matrix, (o1, o2) -> o1[0] - o2[0]);
        if (matrix[0][0] > s) {
            System.out.println(-1);
            return;
        }
        int ans = 1;
        int p = s;
        int max = matrix[0][1];
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] > max) {
                System.out.println(-1);
                return;
            }
            if (matrix[i][0] > p) {
                p = max;
                ans++;
            }
            max = Math.max(matrix[i][1], max);
            if (max >= t) {
                System.out.println(ans);
                return;
            }
        }
        System.out.println(-1);
    }
}



TreeMapkey 存放最右侧的端点,value 存放右端点个数。

先进行右端点从小到大排序,这样后面的区间右端点都是比前面的大,无论后面的区间左端点有多「左边」都无所谓,通过 TreeMap 查找有没有比当前区间的左端点的小的 entry

  1. 如果有则他们合并,更新 TreeMap,减少一个 value 的个数(为 0 则直接删除),添加一个新的右端点入 TreeMap(这里需要用 getOrDefault 方法先查是不是已经有了,有的话需要 + 1,没有的话就是 1);
  2. 如果没有则新起一个 entry(这里需要用 getOrDefault 方法先查是不是已经有了,有的话需要 + 1,没有的话就是 1),另外 ans++
import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(sc.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i] = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
        int ans = 1;
        TreeMap<Integer, Integer> set = new TreeMap<>();
        set.put(arr[0][1], 1);
        for (int i = 1; i < n; i++) {
            Map.Entry<Integer, Integer> e = set.lowerEntry(arr[i][0]);
            if (e != null) {
                int k = e.getKey();
                int v = e.getValue();
                set.remove(k);
                if (v > 1) {
                    set.put(k, v - 1);
                }
            } else {
                ans++;
            }
            int cnt = set.getOrDefault(arr[i][1], 0);
            set.put(arr[i][1], cnt + 1);
        }
        System.out.println(ans);
    }
}


活动打卡代码 AcWing 906. 区间分组

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(sc.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i] = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
        int ans = 1;
        TreeMap<Integer, Integer> set = new TreeMap<>();
        set.put(arr[0][1], 1);
        for (int i = 1; i < n; i++) {
            Map.Entry<Integer, Integer> e = set.lowerEntry(arr[i][0]);
            if (e != null) {
                int k = e.getKey();
                int v = e.getValue();
                set.remove(k);
                if (v > 1) {
                    set.put(k, v - 1);
                }
            } else {
                ans++;
            }
            int cnt = set.getOrDefault(arr[i][1], 0);
            set.put(arr[i][1], cnt + 1);
        }
        System.out.println(ans);
    }
}


活动打卡代码 AcWing 906. 区间分组

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(sc.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i] = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
        int ans = 1;
        TreeMap<Integer, Integer> set = new TreeMap<>();
        set.put(arr[0][1], 1);
        for (int i = 1; i < n; i++) {
            Map.Entry<Integer, Integer> e = set.lowerEntry(arr[i][0]);
            if (e != null) {
                int k = e.getKey();
                int v = e.getValue();
                set.remove(k);
                if (v > 1) {
                    set.put(k, v - 1);
                }
            } else {
                ans++;
            }
            int cnt = set.getOrDefault(arr[i][1], 0);
            set.put(arr[i][1], cnt + 1);
        }
        System.out.println(ans);
    }
}



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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(sc.readLine());
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i] = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);
        int prev = arr[0][1];
        int ans = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i][0] > prev) {
                ans++;
                prev = arr[i][1];
            }
        }
        System.out.println(ans);
    }
}