多重循环问题做时间的优化

img

img

我的代码是这样的

#include 
using namespace std;
const int N = 200010;
int day[N];
int tree[N],res[N]; // 
int n,m,k;
int main()
{
    cin >> n >> m >> k;
    for(int i = 1;i <= m;i ++)    // 天数
    {
        //每天固定加一
        int op,x;
        cin >> op >> x;
        if(op == 1)
        {
            res[x] = k;
        }
        else if(op == 2)
        {
            res[x] = 0;
        }
        else if(op == 3)
        {
            cout<for(int j = 1; j <= n;j ++)
        {
            tree[j] ++;
            if(res[j] != 0)
            {
                tree[j] ++;
                res[j] --;
            }
        }
        
        
    }
    
}

请问，如何做时间的优化使其通过，或者其他思路解决也行

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
这份代码的时间复杂度为 $O(nm)$，其中 $n$ 表示每天的树木数量，$m$ 表示天数。可以看到代码中有两层循环，所以时间复杂度比较高。

对于这个问题，可以考虑使用差分的思想进行优化。我们可以用一个数组 $day$ 记录每天树木的数量变化量，$day[i]$ 表示第 $i$ 棵树在当天的数量变化量。然后我们根据 $day$ 数组来更新每天的树木数量，最后输出第 $x$ 棵树的数量即可。

具体实现步骤如下：

1、初始化 $day$ 数组为全零。
2、对于每天输入的操作，根据操作类型和编号修改 $day$ 数组：
    a. 如果是操作类型 $1$，则将 $day[x]$ 加上 $k$，表示第 $x$ 棵树在当天增加 $k$ 个。
    b. 如果是操作类型 $2$，则将 $day[x]$ 减去之前的值，表示第 $x$ 棵树在当天数量不变。
    c. 如果是操作类型 $3$，则需要输出第 $x$ 棵树在当天的数量。
3、对于每天，遍历一遍 $day$ 数组，累加每棵树当天的变化量，得到每棵树最终的数量，并将其更新到 $tree$ 数组中。

这样做的时间复杂度为 $O(m+n)$，相比之前的方法有很大的提升。以下是实现代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int day[N], tree[N];

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1) day[x] += k;
        else if (op == 2) day[x] -= day[x];
        else if (op == 3) cout << tree[x] << endl;
    }

    for (int i = 1; i <= n; i++)
    {
        tree[i] = day[i];
        if (i > 1) tree[i] += tree[i-1];
        cout << tree[i] << " ";
    }
    cout << endl;

    return 0;
}

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢

灰之魔女不是伊蕾雅，是伊蕾娜！！
因为一天只能操作一次，所以每天都遍历一次是不划算的。树生长的高度等于树自然生长的高度加上树额外生长的高度。自然生长的高度就是i，只需要记录树额外生长的高度即可。树额外生长的高度等于魔法的持续时间，可以用一个数组记录树额外生长的高度，一个数组记录施魔法的时间，一个数组记录魔法结束时间，直接把3个数组合并成一个结构体数组。代码如下：

#include <bits/stdc++.h>
#define min(a,b) (a<b?a:b)
using namespace std;
const int N = 200010;

struct{
    int dh;//额外生长高度
    int st;//魔法开始时间 
    int et;//魔法结束时间 
}tree[N]={{0,0,0}};

int main() {
    int i,n,m,k,op,x;
    cin>>n>>m>>k;
    for(i=0;i<m;i++){
        cin>>op>>x;
        switch (op) {
            case 1:
                //在魔法效果覆盖前，把之前的魔法效果结算一下 
                tree[x].dh+=min(tree[x].et,i)-tree[x].st;
                tree[x].st=i;
                tree[x].et=i+k;
                break;
            case 2:
                //取消魔法效果时，把魔法效果结算一下，并把魔法结束日期和生效日期都设为0
                tree[x].dh+=min(tree[x].et,i)-tree[x].st;
                tree[x].et=tree[x].st=0; 
                break;
            case 3:
                //查询树的高度之前，把魔法效果结算一下，并把魔法开始日期设置为结算日期
                tree[x].dh+=min(tree[x].et,i)-tree[x].st;
                tree[x].st=min(tree[x].et,i);
                cout<<i+tree[x].dh<<endl;
                break;
        }
    }
}

循环一层，时间复杂度为O(m)
这个是运行结果：

img