题解 | #异次元空间#

一.题目描述
NC567异次元空间
数组a表示n个异次元空间的暗物质数量，每天每个异次元空间的暗物质数量会增加d数组中对应元素的值，可以选择冻结空间使之每天不再增加，也可以选择解除冻结，如果异次元空间的暗物质数量大于等于P，会对P取余，P一定为质数，最少可以在第几天的晚上有不少于m个异次元空间有刚好k个暗物质。
图片说明
二.算法(数学)

上面是博主的推导过程(字丑勿怪)，下面是对其进行解释。首先对于每一个异空间可以进行两种选择就是冻结和解除冻结，所以对于每一个异空间刚好有k个暗物质物质是独立了，所以对于每一个异空间什么时候是刚好是k个暗物质是可以计算的(这块可以参考上面图片的推导，涉及到同余和拓展欧几里得求逆元)。对于同余的推导读者可能容易看懂，下面来讲一下拓展欧几里得求逆元，下面给出拓展欧几里得的模板代码和一些简单的介绍(只是简单的介绍一下，要是要真正理解还需要自己去看一下)

//逆元：逆元素是指一个可以取消另一给定元素运算的元素
void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return ;
    }
    exgcd(b,a%b,y,x);
    y-=x*(a/b);    
   //其中x的返回值就是a在取余b情况下的逆元
}

了解了拓展欧几里得求逆元的方法，对于这道题目思路就简单了，求出使每一个异次元空间的暗物质刚好有k个暗物质的天数，我们找出其中的第m个返回就可以了，下面使完整代码：

class Solution {
public:
    void exgcd(int a,int b,long &x,long &y){
        if(b==0){
            x=1;
            y=0;
            return ;
    }
    exgcd(b,a%b,y,x);
    y-=x*(a/b);    
       //其中x的返回值就是a在取余b情况下的逆元
    }
    int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
        vector<int>num; //对每个异次元空间达到k最少天数进行记录
        for(int i=0;i<n;i++){
            if(a[i] == k){
                num.push_back(0);//开始就已经符合了 不需要冻结和释放
            } else{
                long x=0,y=0;
                exgcd(d[i],P,x,y);//按照公式推导的求d[i]的逆元
                long ans=((k-a[i])*x%P+P)%P;//按照公式求每个异次元的最少天数
                num.push_back(ans);
            }
        }
        //找到第m个并返回
        sort(num.begin(),num.end()); 
        return num[m - 1];
    }
};

时间复杂度： $O(nlogn)$ 只需要遍历一遍数组，对每一个数求逆元，求逆元的复杂度是 $logn$ 。
空间复杂度： $O(n^{2})$ 需要额外开辟空间来储存每一个暗物质需要的天数并且拓展欧几里得递归调用栈的空间复杂度是n
优缺点：需要数学推导，但是代码实现简单容易实现。
三.算法(利用java实现)
同样可以利用java实现，下面是完整代码：

import java.util.*;
public class Solution {
    PriorityQueue<Integer> q=new PriorityQueue<>(Comparator.reverseOrder());
    //利用一个优先队列来维护第m小的元素 确保最后返回的元素是第m小元素
    long[] exgcd(int x, int y) {
        //拓展欧几里得公式求逆元 最后返回的[1]是x的逆元
        if (y==0) return new long[]{x,1,0};
        long[] ans=exgcd(y,x%y);
        return new long[]{ans[0],ans[2],ans[1]-ans[2]*(x/y)};
    }
    public int solve (int n, int m, int P, int[] a, int[] d, int k) {
        int res=0;
        for(int i=0;i<n;i++){
            int num = 0;
            //要是开始就是k直接就是0
            if(a[i]==k){
                q.add(0);
            } else {
                long ans=exgcd(d[i],P)[1];
                num=(int)(((k-a[i])*ans%P+P)%P);
                q.add(num);
            }
            //队列的数量大于m的时候就会将队头出队 来维护
            if(q.size()>m){
                q.poll();
            }
        }
        //返回队头
        return q.peek();
    }
}

时间复杂度： $O(nlogn)$ 只需要遍历一遍数组，对每一个数求逆元，求逆元的复杂度是 $logn$ 。
空间复杂度： $O(n^{2})$ 需要额外开辟空间来储存每一个暗物质需要的天数并且拓展欧几里得递归调用栈的空间复杂度是n
优缺点：需要数学推导，利用优先队列维护本质和算法二一样，但是不需要排序，思路较为优。