思路：
题目的主要信息：
- 数组a表示n个异次元空间的暗物质数量，每天每个异次元空间的暗物质数量会增加d数组中对应元素的值
- 可以选择冻结空间使之每天不再增加，也可以选择接触冻结
- 如果异次元空间的暗物质数量大于等于P，会对P取余，P一定为质数
- 最少可以在第几天的晚上有不少于m个异次元空间有刚好k个暗物质
方法一：二分法（超时）
具体做法：
每个空间的增加天数最多次，即
到
天之内不断取模
，它必定会增加到刚好k个暗物质。
我们可以从到
使用二分法，每次检查中间值mid是否满足m个异次元空间在mid天内刚好到达k个暗物质，若可以则缩小右界，若是不行则缩小扩大左界。
class Solution {
public:
int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
int left = 0;
int right = P;
while(left <= right){ //二分法
int mid = (left + right) / 2; //取中间只
int count = 0;
vector<int> b = a;
for(int i = 0; i < n; i++){ //判断有多少个元素已经可以达到k个暗物质
if (a[i] == k) //初始即达到了
count++;
else {
bool flag = false;
for (int j = 0; j < mid; j++) { //判断mid次内能否刚好到k
b[i] = (b[i] + d[i]) % P;
if (b[i] == k) {
flag = true;
break;
}
}
if (flag)
count++;
}
}
if(count >= m)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
};复杂度分析：
- 时间复杂度：
，首先二分法，即外循环是
，内循环每次都要检查n个元素，每次检查最多需要遍历mid次，即
，最坏情况下mid一直往右界上加即
- 空间复杂度：
，辅助数组b的长度
方法二：数学+扩展欧几里得算法
具体做法：
我们可以对上述题意进行数学分析，我们设数组res表示每个异次元空间达到刚好k个暗物质所需最少天数。
则我们有，我们要找的是不少于m个
，可以求出所有的异次元空间所需最少天数，然后进行排序，找到第m个。
现在我们看看如何求每个元素的。对上述公式进行变换得到：
，
这个符号为无条件等于即恒等。
因此，，公式中
即
都是已知的，我们只要求出
即可得到
。
我们都知道，令
即
的逆元，因为P为质数，根据
性质：一个数有逆元的充分必要条件是gcd(x,P)=1,此逆元唯一存在。，我们可以用扩展欧几里得算法求得逆元：
扩展欧几里得算法流程图如下：
class Solution {
public:
void ex_gcd(int a, int b, long& x, long& y){//扩展欧几里得算法
if(b == 0){
x = 1;
y = 0;
return;
}
ex_gcd(b, a % b, y, x); //辗转相除
y -= a / b * x;
}
int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
vector<int> res(n); //每个异次元空间达到k最少天数
for(int i = 0; i < n; i++){
if(a[i] == k) //直到到达，不用增加
res[i] = 0;
else{
long x = 0, y = 0;
ex_gcd(d[i], P, x, y);
res[i] = ((k - a[i]) * x % P + P) % P; //公式
}
}
sort(res.begin(), res.end()); //排序找第m个
return res[m - 1];
}
};复杂度分析：
- 时间复杂度：
，遍历数组对每一个元素进行扩展欧几里得算法，扩展欧几里得函数的时间复杂度为
，
和
分别为函数中的参数，最坏复杂度取参数最大值即
、
，最后还有一个sort函数排序。
- 空间复杂度：
，辅助数组res长度为
，扩展欧几里得函数递归栈为
京公网安备 11010502036488号