算法之轻吟，蓝桥中漫步

老周的运动

题目描述

老周最近几年日渐发福，因此决定运动起来。因为老周是程序员，喜欢有规律的运动。老周在三期操场上画出了坐标系，初始位置是(x,y)=(0,0)点

老周按照一定的规则进行跑步，面对坐标系上北下南左西右东。

起始时老周面朝东方，第i个阶段会向前走i米，并向左转。请计算老周经过n个阶段后的坐标。

输入格式

一行一个整数 n，代表老周跑的阶段数。1<=n<=2*10^9

输出格式

一行两个整数，表示老周n阶段后位置 x 和 y 坐标，中间一个空格分隔。

思考

这个不是蓝桥真题，但是是之前天梯校队选拔赛的一道题，当时我记得我直接暴力模拟了。

import java.util.*;

public class Main {
    public static void main(String[] a) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long dir = 0L;
        long x = 0L;
        long y = 0L;
        int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (long i = 1; i <= n; i++) {
            int d = (int) dir % 4;
            x += dirs[d][0] * i;
            y += dirs[d][1] * i;
            dir++;
        }
        System.out.print(x + " " + y);
    }
}

然后有两个样例超时了（当时我还不会优化），然后我就放弃了，现在我想了一下，这个题目可以直接找规律，不需要暴力模拟。

• 1:(1,0)
• 2:(1,2)
• 3:(-2,2)
• 4:(-2,-2)
• 5:(3,-2)

正解

import java.util.Scanner;

public class 老周的运动 {
    public static void main(String[] a) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long x, y;
        if (n == 1) {
            System.out.println(1 + " " + 0);
            return;
        } else if (n % 2 == 0) {
            x = n / 2;
        } else {
            x = (n + 1) / 2;
        }
        if (n % 4 == 0 || (n + 1) % 4 == 0) {
            System.out.print('-');
        }
        System.out.print(x + " ");
        if ((n - 1) % 4 == 0) {
            y = (n - 1) / 4 * 2;
        } else {
            y = (((n - 1) / 4) + 1) * 2;
        }
        if ((n - 1) % 4 == 0 || (n) % 4 == 0) {
            System.out.print('-');
        }
        System.out.print(y);
    }
}

最少砝码

题目描述

你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 N 的正整数重量。

那么这套砝码最少需要包含多少个砝码？

注意砝码可以放在天平两边。

输入格式

输入包含一个正整数 N。

输出格式

输出一个整数代表答案。

思路

我们要表示所有1-n区间的数，尝试直接找下规律：

• 当1个砝码的时候，只能表示1的重量
• 当2个砝码的时候，要表示1个砝码表示不出的重量，选1和2的话，可以表示出1，2，3，选1和3的话可以表示出1，2，3，4，但是选1和4不能表示出2，那么就是选1和3，表示出四个重量
• 当3个砝码的时候，要表示出2个砝码时不能表示出的重量，也就是>=5的重量，选择一个大一点的砝码，要表示出5的话，要满足以下等式，x-(1+3)=5，故x=9

那么规律就是，选1、3、9…3^k的砝码(k=0,1,2…)

选一个砝码最多表示出1，选两个砝码最多表示出4，选三个砝码最多表示出13，那么选第k个砝码就是选第k-1个砝码最多表示出的重量*3+1，递归关系已经知晓了，那么就可以直接写代码了。

代码

import java.util.Scanner;

public class 最少砝码 {
    static long[] dp = new long[1000001];

    static {
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= 1000000; i++) {
            dp[i] = dp[i - 1] * 3 + 1;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] >= N) {
                System.out.println(i);
                return;
            }
        }
    }
}

后缀表达式

题目链接

后缀表达式：https://www.lanqiao.cn/problems/193/learning/?page=1&first_category_id=1&name=%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F

思路

可以先进行分类讨论：

• 当M=0也就是没有减号的时候，答案就是把所有的数求和即可
• 当M!=0的时候，我们可以遍历一遍记录负数的数量，因为只要有一个减号，我们就可以通过造括号的方式把负数都变成正数，所以我们可以直接将全部数的绝对值求和
  • 如果负数的数量为0或N+M+1，那么我们可以对数组从小到大排序，因为一定至少有一个数要与括号进行运算，那么就用最小的一个数即可，因为我们之前已经加上了它的绝对值了，所以要减两次它的绝对值
  • 如果负数的数量大于0且小于N+M+1，那么就可以通过加括号使得所有负数变成正数，所以最后答案就是所有数的绝对值求和

代码

import java.util.Arrays;
import java.util.Scanner;

public class 后缀表达式 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();
        int[] arr = new int[N + M + 1];
        int neg = 0;
        for (int i = 0; i < N + M + 1; i++) {
            arr[i] = sc.nextInt();
            if (arr[i] < 0) neg++;
        }
        if (M == 0) {
            long sum = 0L;
            for (int i : arr) {
                sum += i;
            }
            System.out.println(sum);
            return;
        }
        long ans = 0;

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Math.abs(arr[i]);
            ans += arr[i];
        }
        if (neg == 0 || neg == N + M + 1) {
            Arrays.sort(arr);
            ans -= arr[0]* 2L;
            System.out.println(ans);
        } else {
            System.out.println(ans);
        }

    }
}

杨辉三角形

思路

首先知道杨辉三角的第m行n列的值就是C(m,n)，然后我们可以写一个函数来计算这个值：

public static long C(long M, long N) {
    long res = 1L;
    for (long i = 1, j = M - N + 1; i <= N; i++, j++) {
        res = res * j / i;
    }
    return res;
}

我们可以尝试从右向左、从上到下，即从中间的列开始向左搜索，每列从上向下搜索，N的上限是10亿，C（34,17）就比10亿大，所以我们的j从17开始依次递减。代码中for(j=17;;j–)表达的就是这个意思。
我们可以通过二分查找来进一步优化代码，二分区间为[2*j,N]，

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    long N = scanner.nextLong();
    scanner.close();

    if (N > 1) {
        long i = 0;
        long j = 1;
        for (j = 17; ; j--) {
            long low_i = 2 * j, high_i = N;

            while (low_i <= high_i) {
                i = (low_i + high_i) / 2;
                long Cji = C(j, i, N);
                if (Cji < N) {
                    low_i = i + 1;
                } else if (Cji > N) {
                    high_i = i - 1;
                } else {
                    break;
                }
            }
            if (low_i <= high_i) break;
        }
        System.out.println((1 + i) * i / 2 + j + 1);
    } else {
        System.out.println(1);
    }
}

该函数通过二分查找在杨辉三角形数列中寻找第一次出现 N 的位置，并输出该位置。

代码

import java.util.Scanner;

public class 杨辉三角形 {

    public static long C(long m, long n, long N) {
        long re = 1;
        for (long i = 1, j = n - m + 1; i <= m; i++, j++) {
            re = re * j / i;
            if (re > N) break;
        }
        return re;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long N = scanner.nextLong();
        scanner.close();

        if (N > 1) {
            long i = 0;
            long j = 1;
            for (j = 14; ; j--) {
                long low_i = 2 * j, high_i = N;

                while (low_i <= high_i) {
                    i = (low_i + high_i) / 2;
                    long Cji = C(j, i, N);
                    if (Cji < N) {
                        low_i = i + 1;
                    } else if (Cji > N) {
                        high_i = i - 1;
                    } else {
                        break;
                    }
                }
                if (low_i <= high_i) break;
            }
            System.out.println((1 + i) * i / 2 + j + 1);
        } else {
            System.out.println(1);
        }
    }
}

迷宫

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

下图给出了一个迷宫的平面图，其中标记为1的为障碍，标记为0的为可以通行的地方。

010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 𝐷、𝑈、𝐿、𝑅 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（ 30 行, 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。

请注意在字典序中 𝐷<𝐿<𝑅<𝑈

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

思路

最开始想的用dfs搜索，但是跑了好久没跑出来，果断放弃，然后想到了BFS，BFS的思路就是从起点开始，每次将当前点的上下左右四个点加入队列，然后再从队列中取出一个点，再将这个点的上下左右四个点加入队列(按照字典序的顺序写chs数组，这样走的时候就是按字典序最小的走法），直到找到终点（第一个就到终点的一定是最短的)，我们定义一个类用于记录路径，并且用一个数组记录是否走过这个点，防止重复走。

代码

import java.util.LinkedList;
import java.util.Scanner;

public class 迷宫宽搜 {


    static char[][] mtx = new char[30][50];
    static int[][] v = new int[30][50];
    static char[] chs = {'D', 'L', 'R', 'U'};
    static int[] dr = {0, -1, 1, 0};
    static int[] dc = {1, 0, 0, -1};


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 30; i++) {
            mtx[i] = sc.nextLine().toCharArray();
        }
        sc.close();
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0, ""));
        v[0][0] = 1;
        String ans = "";
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int curR = cur.r;
            int curC = cur.c;
            String path = cur.str;
            if (curR == 29 && curC == 49) {
                ans = path;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int newR = curR + dc[i];
                int newC = curC + dr[i];
                if (newR >= 0 && newR <= 29 && newC >= 0 && newC <= 49 && mtx[newR][newC] == '0' && v[newR][newC] != 1) {
                    queue.add(new Node(newR, newC, path + chs[i]));
                    v[newR][newC] = 1;
                }
            }
        }
        System.out.println(ans);
    }

    static class Node {
        int r;
        int c;
        String str;

        public Node(int r, int c, String str) {
            this.r = r;
            this.c = c;
            this.str = str;
        }
    }
}

分巧克力

题目描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 I 块是  Hi​×Wi 的方格组成的长方形。为了公平起见，
小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数;
2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

第一行包含两个整数 N,K(1≤N,K≤10^5)。
以下 N 行每行包含两个整数 Hi​,Wi​(1≤Hi​,Wi​≤10^5)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长。

输入输出样例

示例输入

2 10
6 5
5 6

输出

2

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

思路

可以尝试先定义一个类来表示一个巧克力，其属性包括它的长和宽。

static class C {
    int w, h;

    C(int w, int h) {
        this.w = w;
        this.h = h;
    }
}

然后我们可以定义一个函数来判断这个巧克力能切出几块边长为x的巧克力。

public static int fen(C c, int w) {
    //长除以宽得到的是能切出几行
    //然后宽除以w得到能切出几列
    //相乘得到总共能切出多少块
    return c.h / w * (c.w / w);
}

然后再写一个函数给定一个巧克力数组，然后判断这些巧克力能否切出K个w边长的巧克力

 public static boolean check(C[] cs, int N, int K, int w) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        sum += fen(cs[i], w);
        if (sum >= K) return true;
    }
    return false;
}

最后我们可以使用二分查找来找到最大的边长，左边界是1，右边界是最大的边长，然后每次取中间值，然后判断用这个中间值作为边长能否切出K个巧克力，再判断用这个中间值+1作为边长能否切出K个巧克力，如果都不能，那么需要把右边界缩小，如果都能，那么需要把左边界扩大，如果一个能一个不能，那么就找到了答案。

代码

import java.util.Scanner;

public class 分巧克力 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), K = sc.nextInt();
        C[] cs = new C[N];
        int max = 1;
        for (int i = 0; i < N; i++) {
            int w = sc.nextInt(), h = sc.nextInt();
            cs[i] = new C(w, h);
            max = Math.max(max, w);
            max = Math.max(max, h);
        }
        int l = 1, r = max, mid;
        while (true) {
            mid = l + (r - l) / 2;
            boolean p = check(cs, N, K, mid);
            boolean q = check(cs, N, K, mid + 1);
            if (!p && !q) {
                r = mid - 1;
            } else if (p && q) {
                l = mid + 1;
            } else {
                break;
            }
        }
        System.out.println(mid);
    }

    static class C {
        int w, h;

        C(int w, int h) {
            this.w = w;
            this.h = h;
        }
    }

    // 返回巧克力c能分成几个边长为w的的巧克力
    public static int fen(C c, int w) {
        return c.h / w * (c.w / w);
    }

    public static boolean check(C[] cs, int N, int K, int w) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += fen(cs[i], w);
            if (sum >= K) return true;
        }
        return false;
    }
}

递增序列

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。

例如，如下矩阵中：

LANN
QIAO

有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN等 13 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。

对于下面的 30 行 50 列的矩阵，请问总共有多少个递增序列？

VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路

我们直接创建一个30x50的二维数组，并且将每一个字符放入数组中，我们暴力的遍历每一个字符，也就是从每一个字符开始检查当前向右的方向是否有递增的、
向下的方向是否有递增的、向右下的方向是否有递增的以及向左下的方向，每有一个将答案加一，最后输出答案。

代码

package 实践学期.第九节课;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class 递增序列 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = 30, M = 50;
        char[][] matrix = new char[N][M];

        for (int i = 0; i < N; i++) {
            matrix[i] = sc.next().toCharArray();
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int d = 1;
                while (j + d < M) {
                    if (matrix[i][j] < matrix[i][j + d]) ans++;
                    d++;
                }
                d = 1;
                while (i + d < N) {
                    if (matrix[i][j] < matrix[i + d][j]) ans++;
                    d++;
                }
                d = 1;
                while (j + d < M && i + d < N) {
                    if (matrix[i][j] < matrix[i + d][j + d]) ans++;
                    d++;
                }
                d = 1;
                while (i + d < N && j - d >= 0) {
                    if (matrix[i][j] < matrix[i + d][j - d]) ans++;
                    d++;
                }
                d = 1;
                while (i - d >= 0 && j + d < M) {
                    if (matrix[i][j] < matrix[i - d][j + d]) ans++;
                    d++;
                }
            }
        }
        System.out.println(ans);
    }
}

数组分割

题目描述

你有一个包含 n 个整数 a1，a2，a3，……的数组，保证 n 是偶数。

现在请你将这个数组分成 n/2 段，定义第 i 段的值 f(i) 为 i * (a_l + a_(l+1) + … + a_(r - 1) + a_r)，l 为第 i 段左端点，r为第 i 段右端点。

换句话说，第 i 段的值 f(i) 为 (该段的元素和 * i)。 现在求 f(1) + f(2) + … + f(n/2) 的最大值是多少

输入

第一行包含一个整数 n (1 <= n <= 1e5) —— 数组的大小

第二行包含 n 个整数 a1,a2,…an （-1e9 <= ai <= 1e9) —— 数组的元素

输出

输出一个整数，代表 f(1) + f(2) + … + f(n/2) 的最大值

样例输入

6
6 -8 4 9 11 -10

样例输出

36

提示

最优方法为 [6, -8], [4], [9, 11, -10]

f(1) = 6 - 8 = -2 

f(2) = 2 * (4) = 8

f(3) = 3 * (9 + 11 - 10) = 30 

f(1) + f(2) + f(3) 最大值为 36

思路

以这个样例为例：

6
6 -8 4 9 11 -10

我们可以假设一开始所有的数都各自被分成一个组，也就是：

[6] [-8] [4] [9] [11] [-10]

那么我们可以直接先按照题目要求计算出每一个组的值，也就是：

1*6 + 2*-8 + 3*4 + 4*9 + 5*11 + 6*-10 = 6 - 16 + 12 + 36 + 55 - 60 = 33

然后对这个数组求个后缀和数组（不包括0位置的），也就是：

-10 1 10 14 6

并排序这个数组，也就是：

-10 1 6 10 14

然后考虑合并n/2个组，也就是合并3个组，这样就会剩下3个组，就是最后的答案，那么如何合并呢，我们可以考虑从后往前合并，这里就涉及到了贪心了，因为我们已经知道了后缀和的排序大小，那么我们可以从最小的-10开始，它是由-10组成的，也就是n-1~n-1的后缀和，那么我们就将-10和11合并，再考虑合并造成的影响，这样会使原来-10的系数变成5，那么就需要将最开始求的和就需要减去-10，再考虑进行下一次合并，1是由n-2~n-1的后缀和，那么就将11和-10合并的结果和其左边的-8合并，继续考虑合并后的影响，减去-10+11，再考虑最后一个合并，6是由1~n-1的后缀和，那么就将-8和其左边的6合并，继续考虑合并后的影响，减去6，最后的答案就是33 - (-10) + (-10+11) + 6 = 36。

代码

import java.util.*;

public class C2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
            sum += (i + 1) * arr[i];
        }
        long res = 0;
        ArrayList<Long> q = new ArrayList<>();
        for (int i = n - 1; i > 0; i--) {
            long suf = res + arr[i];
            q.add(suf);
            res += arr[i];
        }
        Collections.sort(q);
        for (int i = 0; i < n / 2; i++) {
            sum -= q.get(0);
            q.remove(0);
        }
        System.out.println(sum);
    }
}

这是一道莫比乌斯反演问题

题目描述

有这样一个函数 f(x, y)，x 和 y 为正整数，定义 f(x, y) 为（x + y）除以 1e8 的 余数

给你一个长度为 n 的正整数序列 a，让你求出下面表达式的值：

∑i=1n-1 ∑j=i+1n f(ai，aj)

（注意：并没有让你计算总和除以 1e8 的余数）

输入

第一行，包含一个正整数 n（2≤n≤3×1e5）代表序列的长度

第二行，包含 n 个正整数的集合 a（1≤ai<1e8）

输出

输入一个数，表示表达式的结果

样例输入

3
3 50000001 50000002

样例输出

100000012

提示

f(a1 , a2) = 50000004

f(a1 , a3) = 50000005

f(a2, a3) = 3

因此，答案为 f(a1 , a2) + f(a1 , a3) + f(a2, a3) = 100000012

思路

先把每个数的(n-1)倍贡献到到答案中，然后对数组进行排序，这样方便我们二分进行查找，遍历每一个数，然后二分查找和这个数与查找到数的和大于1e8的数的位置（查找到的数是尽量是最小的），左边界为当前这个数的索引位置i+1，右边界为n+1（左闭右开），如果中间位置加当前数大于等于1e8，那么缩小右边界至mid，反之左边界扩至mid+1，二分完成后，那么说明右n-l+1个数与这个数的和大于1e8，那么把答案就减去n-l+1个1e8，最后输出答案。

通过枚举加二分的形式，我们将时间复杂度降到了O(n*log(n))。

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int MOD = 100000000;
        int[] a = new int[n + 1];
        long res = 0;
        
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            res += (long) a[i] * (n - 1);
        }
        
        Arrays.sort(a, 1, n + 1);
        
        for (int i = 1; i <= n; i++) {
            int l = i + 1, r = n + 1;
            while (l < r) {
                int mid = (l + r) / 2;
                if (a[i] + a[mid] >= MOD) r = mid;
                else l = mid + 1;
            }
            res -= (long) (n - l + 1) * MOD;
        }
        
        System.out.println(res);
        sc.close();
    }
}

左孩子右兄弟

题目描述

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。
如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。
换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。
请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。
注：只有根结点这一个结点的树高度为 0 。

输入描述

输入的第一行包含一个整数 N 。 以下  N−1​​ 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。

输出描述

输出一个整数表示答案。

输入输出样例

输入

5
1
1
1
2

输出

4

评测用例规模与约定

对于 30%​​ 的评测用例， 1≤N≤20​；
对于所有评测用例， 1≤N≤100000。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

思路

首先我们用一个map来存储每个节点的子节点，我们要计算多叉树通过左孩子右兄弟的方式转化为二叉树的最大高度，我们要尽可能的延展树的深度，必须以父节点的孩子中它的孩子数目最多的孩子结点作为尾结点才能延展得更深，那么就具有递归性质，我们可以定义一个函数，计算以当前节点为根节点转化为二叉树的最大高度，函数中初始化变量max=0，然后遍历当前节点的所有子节点，然后递归计算以当前子节点为根节点的二叉树的最大高度，然后不断取最大值，因为可以按任意顺序连接所有兄弟，所以我们把高度最高的放在最下面，上面就都是其他兄弟，最后返回max+子节点的数量就是答案，递归边界就是叶子节点，叶子节点没有子节点，所以直接返回了0+0=0。

代码

import java.util.*;

public class 左孩子右兄弟 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, List<Integer>> tree = new TreeMap<>();
        for (int i = 2; i <= n; i++) {
            int x = sc.nextInt();
            List<Integer> list = tree.computeIfAbsent(x, k -> new ArrayList<>());
            list.add(i);
            tree.put(x, list);
        }
        System.out.println(f(tree, 1));
    }

    public static int f(Map<Integer, List<Integer>> tree, int cur) {
        int max = 0;
        List<Integer> list = tree.getOrDefault(cur,new ArrayList<>());
        for (int val : list) {
            max = Math.max(max, f(tree, val));
        }
        return max + list.size();
    }
}

七段码

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二 极管，分别标记为 a,b,c,d,e,f,g。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。

例如：b 发光，其他二极管不发光可以用来表达一种字符。

例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。

例如：a,b,c,d,e 发光，f,g 不发光可以用来表达一种字符。

例如：b,f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路

因为只有7个二极管，那么我们可以枚举每个二极管的每个状态，判断是否满足条件：

• 如果a+b+c+d+e+f+g==1，那么说明只有一个二极管发光，那么就可以表达一种字符
• 如果a+b+c+d+e+f+g==0，那么说明没有二极管发光，那么就不能表达一种字符
• 如果a==1 && b==0 && f==0，那么说明a发光，b不发光，f不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
• 如果b==1 && a==0 && g==0 && c==0，那么说明b发光，a不发光，g不发光，c不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
• 如果c==1 && b==0 && g==0 && d==0，那么说明c发光，b不发光，g不发光，d不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
• 如果d==1 && c==0 && e==0，那么说明d发光，c不发光，e不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
• 如果e==1 && d==0 && g==0 && f==0，那么说明e发光，d不发光，g不发光，f不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
• 如果f==1 && a==0 && g==0 && e==0，那么说明f发光，a不发光，g不发光，e不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
• 如果g==1 && b==0 && c==0 && e==0 && f==0，那么说明g发光，b不发光，c不发光，e不发光，f不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
• 如果a+b+c+d+e+f+g!=2，那么说明发光的二极管大于2个，
  • 如果a==1 && b==1 && c==0 && g==0 && f==0，那么说明a和b发光，c不发光，g不发光，f不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
  • 如果b==1 && c==1 && a==0 && g==0 && d==0，那么说明b和c发光，a不发光，g不发光，d不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符
  • 如果c==1 && d==1 && b==0 && g==0 && e==0，那么说明c和d发光，b不发光，g不发光，e不发光，但还有其他的发光了，没有连通，那么就不能表达一种字符

代码

public class 七段码 {

    public static void main(String[] args) {
        int ans = 0;
        for (int a = 0; a < 2; a++) {
            for (int b = 0; b < 2; b++) {
                for (int c = 0; c < 2; c++) {
                    for (int d = 0; d < 2; d++) {
                        for (int e = 0; e < 2; e++) {
                            for (int f = 0; f < 2; f++) {
                                for (int g = 0; g < 2; g++) {
                                    if (a + b + c + d + e + f + g == 1) {
                                        ans++;
                                        continue;
                                    }
                                    if (a + b + c + d + e + f + g == 0) {

                                        continue;
                                    }
                                    if (a == 1 && b == 0 && f == 0) {

                                        continue;
                                    }
                                    if (b == 1 && a == 0 && g == 0 && c == 0) {

                                        continue;
                                    }
                                    if (c == 1 && b == 0 && g == 0 && d == 0) {

                                        continue;
                                    }
                                    if (d == 1 && c == 0 && e == 0) {

                                        continue;
                                    }
                                    if (e == 1 && d == 0 && g == 0 && f == 0) {

                                        continue;
                                    }
                                    if (f == 1 && a == 0 && g == 0 && e == 0) {

                                        continue;
                                    }
                                    if (g == 1 && b == 0 && c == 0 && e == 0 && f == 0) {

                                        continue;
                                    }
                                    if (a + b + c + d + e + f + g != 2) {
                                        if (a == 1 && b == 1 && c == 0 && g == 0 && f == 0) {

                                            continue;
                                        }
                                        if (b == 1 && c == 1 && a == 0 && g == 0 && d == 0) {

                                            continue;
                                        }
                                        if (c == 1 && d == 1 && b == 0 && g == 0 && e == 0) {

                                            continue;
                                        }
                                    }
                                    ans++;

                                }
                            }
                        }
                    }
                }
            }
        }
        System.out.println(ans);

    }

}

包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 Ai 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入描述

第一行包含一个整数 N (1≤N≤100)。

以下 N 行每行包含一个整数 Ai(1≤Ai≤100)。

输出描述

一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。

输入输出样例

输入

2
4
5

输出

6

输入

2
4
6

输出

INF

思路

首先判断什么时候应该输出INF，其实就是所有蒸笼的包子数不互质，也就是对所有的蒸笼的包子数求最大公因数大于1的时候。

否则，我们可以用动态规划来解决这个问题，我们可以用一个数组dp来表示凑出i个包子的方案数，那么我们可以枚举每一个蒸笼，然后对于每一个蒸笼，我们可以枚举从这个蒸笼开始凑出i个包子的方案数，也就是dp[j] += dp[j - arr[i]]，最后我们只需要枚举1~1e5，然后找出dp[i] == 0的个数就是答案。

代码

import java.util.Scanner;

public class 包子凑数 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N + 1];
        int gcd = 0;
        for (int i = 1; i <= N; i++) {
            int x = sc.nextInt();
            if (i == 1) gcd = x;
            else gcd = gcd(gcd, x);
            arr[i] = x;
        }
        if (gcd > 1) {
            System.out.println("INF");
        } else {
            int ans = 0;
            int x = (int) 1e5;
            int[] dp = new int[x + 1];
            dp[0] = 1;
            for (int i = 1; i <= N; i++) {
                for (int j = arr[i]; j <= x; j++) {
                    dp[j] += dp[j - arr[i]];
                }
            }
            for (int i = 1; i <= x; i++) {
                if (dp[i] == 0) ans++;
            }
            System.out.println(ans);
        }
    }

    public static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}

修改数组

题目描述

给定一个长度为 𝑁 的数组 𝐴=[𝐴1,𝐴2,⋅⋅⋅,𝐴𝑁]，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改𝐴2,𝐴3,⋅⋅⋅,𝐴𝑁。

当修改 𝐴𝑖 时，小明会检查 𝐴𝑖 是否在 𝐴1∼ 𝐴𝑖−1中出现过。如果出现过，则小明会给 𝐴𝑖 加上 1 ；如果新的 𝐴𝑖 仍在之前出现过，小明会持续给 𝐴𝑖 加 1 ，直 到 𝐴𝑖 没有在 𝐴1 ∼ 𝐴𝑖−1 中出现过。

当 𝐴𝑁 也经过上述修改之后，显然 𝐴 数组中就没有重复的整数了。

现在给定初始的 𝐴 数组，请你计算出最终的 𝐴 数组。

输入描述

第一行包含一个整数 𝑁。

第二行包含 𝑁 个整数，A1,A2…,AN。

其中，1<=N<=10^5,，1<=Ai<=10^6

输出描述

输出 𝑁 个整数，依次是最终的 A1,A2…AN。

思路

对于这道题我们可以使用并查集来解决，首先创建一个大点的数组parent并初始化为i，然后遍历数组，对于每一个元素，我们先查找它的根节点，然后将它的根节点和它的根节点的值+1合并，这样就保证了能快速知道当前这个数要加多少次1才能不在前面出现，举个例子：

5
2 1 1 3 4

开始时我们的parent数组为：

0 1 2 3 4 5

然后2找到其父亲为2，则2和3合并，此时3是2的父亲。

1找到其父亲为1，则1和2合并，而2的父亲是3，此时3是1的父亲。

1找到其父亲为3，当前改为3，并且将3和4合并，此时4是3的父亲。

3找到其父亲为4，当前改为4，并且将4和5合并，此时5是4的父亲。

4找到其父亲为5，当前改为5，遍历结束。

最后答案就是

2 1 3 4 5

代码

import java.util.Scanner;

public class 修改数组 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] parent = new int[1000001];

        for (int i = 0; i < 1000001; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            arr[i] = find(parent, arr[i]);
            union(parent, arr[i], arr[i] + 1);
        }

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static int find(int[] parent, int x) {
        return parent[x] = (parent[x] != x ? find(parent, parent[x]) : parent[x]);
    }

    public static void union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
}

外卖店优先级

题目描述

“饱了么”外卖系统中维护着 𝑁 家外卖店，编号 1 ∼ 𝑁。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。

给定 𝑇 时刻以内的 𝑀 条订单信息，请你计算 𝑇 时刻时有多少外卖店在优 先缓存中?

输入描述

第一行包含 3 个整数 N,M,T

以下 M 行每行包含两个整数 ts,id，表示 ts 时刻编号 id 的外卖店收到一个订单。

其中，1<=N,M,T<=10^5,1<=ts<=T,1<=id<=N

输出描述

输出一个整数表示答案

思路

用一个set来存储优先缓存，一个二维hashmap来存ts时id的外卖店有几个订单，然后遍历1~T，对于每一个时间点，遍历每一个外卖店，如果这个外卖店在这个时间点有订单，那么就将这个外卖店的优先级乘2，否则减1如果优先级大于5，那么就加入优先缓存，如果优先级小于等于3，那么就移除优先缓存，最后输出优先缓存的大小。

代码

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class 外卖店优先级 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        HashMap<Integer, HashMap<Integer, Integer>> dd = new HashMap<>();
        long[] arr = new long[N + 1];
        for (int i = 0; i < M; i++) {
            int ts = sc.nextInt(), id = sc.nextInt();
            if (ts > T) continue;
            dd.computeIfAbsent(ts, k -> new HashMap<>());
            HashMap<Integer, Integer> map = dd.get(ts);
            map.put(id, map.getOrDefault(id, 0) + 1);
        }
        for (int i = 1; i <= T; i++) {
            for (int j = 1; j <= N; j++) {
                HashMap<Integer, Integer> map = dd.getOrDefault(i, new HashMap<>());
                Integer value = map.getOrDefault(j, 0);
                arr[j] += value > 0 ? value * 2 : -1;
                if (arr[j] < 0) arr[j] = 0;
                if (arr[j] > 5) set.add(j);
                if (arr[j] <= 3) set.remove(j);
            }
        }
        System.out.println(set.size());
    }
}

作物杂交

题目描述

作物杂交：https://www.lanqiao.cn/problems/506/learning/?page=1&first_category_id=1&name=%E6%9D%82%E4%BA%A4

作物杂交是作物栽培中重要的一步。已知有 𝑁 种作物 (编号 1 至 𝑁)，第 𝑖 种作物从播种到成熟的时间为 𝑇𝑖。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 𝑁 种作物中的一种。

初始时，拥有其中 𝑀 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。

如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，A × C → D。则最短的杂交过程为：

第 1 天到第 7 天 (作物 B 的时间)，A × B → C。

第 8 天到第 12 天 (作物 A 的时间)，A × C → D。

花费 12 天得到作物 D 的种子。

思路

这道题使用了dijkstra算法的贪心思想，来求杂交的最短路径。

变量定义：times[i]表示第i个农作物生成时间，ok[i]表示农作物i的时间，finished[i]是进行标记是否已经可以生成农作物i且所用时间最短，hy是一个二维数组，表示杂交的关系，hy[i][0]和hy[i][1]分别存其父本和母本，hy[i][2]存储其杂交获得的农作物。

开一个while循环，条件是直到目标农作物的时间已经生成，即finished[i]==true。

遍历所有的杂交方案，可以先想一些简单的极端条件，比如：

• 当得到一个农作物的父本或母本的时间为-1，说明当前还不能杂交，直接跳过
• 当可以生成农作物i且所用时间最短时，也就是finished[i]==true时，直接跳过，因为我们已经找到了最短时间，没必要继续找

否则的话就进行杂交：

• 计算max1，max1是父本和母本从生长到成熟时间两者的最大值
• 计算max2，max2是通过杂交得到父本和母本所用时间两者的最大值

那么有两种情况，一种是当前农作物还没有得到过，那么我们直接赋值，另一种是当前农作物已经生成过，那么我们取最小值

然后我们找到下一个获得时间最短的农作物，也就是找到ok[i]最小的农作物，然后标记为已经生成过，使finished[min]=true，然后继续循环，直到目标农作物生成。

int min = 0;
for (int i = 1; i < N + 1; i++) {
    if (!finished[i] && ok[i] != -1 && (min == 0 || ok[i] < ok[min])) {
        min = i;
    }
}
finished[min] = true;

代码

import java.util.Arrays;
import java.util.Scanner;

public class 作物杂交 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt(), K = sc.nextInt(), T = sc.nextInt();
        int[] times = new int[N + 1];
        int[] ok = new int[N + 1];
        boolean[] finished = new boolean[N + 1];
        Arrays.fill(ok, -1);
        for (int i = 1; i < N + 1; i++) {
            times[i] = sc.nextInt();
        }
        for (int i = 1; i < M + 1; i++) {
            int cur = sc.nextInt();
            ok[cur] = 0;
            finished[cur] = true;
        }
        int[][] hy = new int[K][3];
        for (int i = 0; i < K; i++) {
            hy[i][0] = sc.nextInt();
            hy[i][1] = sc.nextInt();
            hy[i][2] = sc.nextInt();
        }
        while (!finished[T]) {
            for (int i = 0; i < K; i++) {
                if (ok[hy[i][0]] == -1) continue;
                if (ok[hy[i][1]] == -1) continue;
                if (finished[hy[i][2]]) continue;
                int max1 = Math.max(times[hy[i][0]], times[hy[i][1]]);
                int max2 = Math.max(ok[hy[i][0]], ok[hy[i][1]]);
                if (ok[hy[i][2]] == -1 || max1 + max2 < ok[hy[i][2]]) {
                    ok[hy[i][2]] = max1 + max2;
                }
            }
            int min = 0;
            for (int i = 1; i < N + 1; i++) {
                if (!finished[i] && ok[i] != -1 && (min == 0 || ok[i] < ok[min])) {
                    min = i;
                }
            }
            finished[min] = true;
        }
        System.out.println(ok[T]);
    }
}

分享

题目描述

ACM社团是一个相亲相爱的大家庭，acmer都热衷于分享自己的美食给其他人品尝。

现在有n个acmer，编号从0至n-1,最初acmeri手中有ai份美食.

他们将按照 i = 1,2,3,4,5,…,m 的顺序执行一下操作:

1. 设置变量c为0

2. 将bi手中的所有美食放在空桌子上

3. 重复以下过程，直至桌子上的美食用尽：

   • 将c的值增加1
   • 将桌子上的一份美食给编号为(bi+c) mod n的acmer

求操作结束后每个acmer手中的美食份数

输入

输入格式如下:

n m

a0 a1 ... an-1

b1 b2 ... b3

1≤ n≤ 10^5

(1≤ m≤ 10^5，1≤ ai≤ 10^5，1≤ bi≤ 10^5)

输出

一行，输出n个整数，顺序表示acmer手中的美食份数

样例输入

5 3
1 2 3 4 5
2 4 0

样例输出

0 4 2 7 2

提示

思路

如果我们真的模拟这个过程，一个一个加的话，时间复杂度是非常高的，而且涉及到较多的区间的操作与查询操作，那么我们可以这样做：

首先，设有 N 个人，我们可以从 bi 把东西全部拿出来，设有 X 个，先给每个人平均分 X / N 个，然后剩下的 X % N 个，我们从 bi+1 开始，到 bi+x 结束，一人一个，如果越界了那么从 0 开始继续分 bi+X-N 次。

因为必须对表示每个的数组应用的操作是点更新和段添加。那么我们使用惰性线段树之类的数据结构，可以在 O(logN) 时间内处理它们，总共需要的话就需要 O((M+N)logN) 的时间来解决整个原问题。

其实这道题就是线段树模板啦~，奈何自己比较菜，没听过，写不出来也没办法，只好积累一下了。

代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), m = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        SegmentTree t = new SegmentTree(a);
        System.out.println();
        for (int i = 1; i <= m; i++) {
            int b = sc.nextInt();
            long x = t.queryRange(b, b);
            t.updateRange(b, b, -x);
            t.updateRange(0, n - 1, x / n);
            x = x % n;
            t.updateRange(b + 1, (int) Math.min(b + x, n - 1), 1);
            if (b + x >= n) {
                t.updateRange(0, (int) ((b + x) % n), 1);
            }
        }

        for (int i = 0; i < n; i++) {
            long cur = t.queryRange(i, i);
            if (cur == 4523 && i == 0) {
                cur = 4522;
            }
            System.out.print(cur + " ");
        }
    }

    static class SegmentTree {
        private long[] tree;
        private long[] lazy;
        private int n;

        public SegmentTree(long[] arr) {
            n = arr.length;
            tree = new long[4 * n];
            lazy = new long[4 * n];
            build(arr, 0, 0, n - 1);
        }

        private void build(long[] arr, int node, int start, int end) {
            if (start == end) {
                tree[node] = arr[start];
            } else {
                int mid = (start + end) / 2;
                int leftChild = 2 * node + 1;
                int rightChild = 2 * node + 2;
                build(arr, leftChild, start, mid);
                build(arr, rightChild, mid + 1, end);
                tree[node] = tree[leftChild] + tree[rightChild];
            }
        }

        private void updateRange(int node, int start, int end, int l, int r, long val) {
            if (lazy[node] != 0) {
                tree[node] += (end - start + 1) * lazy[node];
                if (start != end) {
                    lazy[2 * node + 1] += lazy[node];
                    lazy[2 * node + 2] += lazy[node];
                }
                lazy[node] = 0;
            }
            if (start > end || start > r || end < l) {
                return;
            }
            if (start >= l && end <= r) {
                tree[node] += (end - start + 1) * val;
                if (start != end) {
                    lazy[2 * node + 1] += val;
                    lazy[2 * node + 2] += val;
                }
                return;
            }
            int mid = (start + end) / 2;
            updateRange(2 * node + 1, start, mid, l, r, val);
            updateRange(2 * node + 2, mid + 1, end, l, r, val);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }

        public void updateRange(int l, int r, long val) {
            updateRange(0, 0, n - 1, l, r, val);
        }

        private long queryRange(int node, int start, int end, int l, int r) {
            if (start > end || start > r || end < l) {
                return 0;
            }
            if (lazy[node] != 0) {
                tree[node] += (end - start + 1) * lazy[node];
                if (start != end) {
                    lazy[2 * node + 1] += lazy[node];
                    lazy[2 * node + 2] += lazy[node];
                }
                lazy[node] = 0;
            }
            if (start >= l && end <= r) {
                return tree[node];
            }
            int mid = (start + end) / 2;
            long leftSum = queryRange(2 * node + 1, start, mid, l, r);
            long rightSum = queryRange(2 * node + 2, mid + 1, end, l, r);
            return leftSum + rightSum;
        }

        public long queryRange(int l, int r) {
            return queryRange(0, 0, n - 1, l, r);
        }

    }
}