首页 > 试题广场 >

异次元空间

[编程题]异次元空间

热度指数：249 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有n个异次元空间，第0天的晚上第i个异次元空间有 $a_i$ 个暗黑物质。

每天早上，第i个异次元空间会增加 $d_i$ 个暗黑物质。

每天中午，如果某异次元空间的暗黑物质数量大于等于 ${P}$ (保证 ${P}$ 为质数),则该异次元空间会有 ${P}$ 个暗黑物质产生反应而消失，直到剩余的暗黑物质少于 ${P}$ 个。

每天晚上，对于每个异次元空间，牛牛都可以选择是否冻结/解冻该空间。当异次元空间被冻结时，这个异次元空间无法继续产生暗黑物质。（第0天晚上也可以进行冻结操作）

现在牛牛想知道，最少可以在第几天的晚上有不少于m个异次元空间有刚好k个暗黑物质。

示例1

输入

3,2,5,[1,0,3],[2,2,1],2

输出

说明

第0天晚上牛牛冻结第二个空间
第一天晚上各个空间物质数量为[3,0,4]，牛牛不进行操作
第二天晚上各个空间物质数量为[0,0,4]，此时牛牛为第二个空间解冻
第三个晚上各个空间物质数量为[2,2,1]，此时已经有两个空间有刚好2个物质，满足条件

备注:



第一个参数n代表异次元空间数目
第二个参数为整数m，含义见题面
第三个参数为整数P，含义见题面
第四个参数vector a包含n个元素代表每个异次元空间一开始的暗黑物质数目
第五个参数vector b包含m个元素代表每个异次元空间每天增加的暗黑物质数目
第六个参数为整数k，含义见题面

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 异次元空间
     * @param n int整型 
     * @param m int整型 
     * @param P int整型 
     * @param a int整型vector 
     * @param d int整型vector 
     * @param k int整型 
     * @return int整型
     */
    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 -= a/b * x;
        return;
    }
    int solve(int n, int m, int P, vector<int>& a, vector<int>& d, int k) {
        int r[n];
        for(int i=0;i<n;i++){
            long x, y;
            exgcd(d[i], P, x, y);
            long t = k - a[i];
            r[i] = (t*x%P + P) % P;
        }
        sort(r, r+n);
        return r[m-1];
    }
};

发表于 2020-09-02 17:08:50 回复(0)

Rain-y

这题目我真是无语了，题目说的 超过 m 个，可给出的示例里就 2 个，还说 刚好 2 个，答案是 3。那行吧，我算你说的是 >= m 。可是到了用例，2,1,131,[103,101],[3,56],37，第一个空间需要 109 晚上，第二个空间需要 55 晚上，按照 >= 1 的话，不是应该是 55 吗？（给出的参考是 109 个，说我不通过）
行吧，你🐂。

发表于 2020-07-30 18:24:17 回复(0)