Luftmensch

用户名：8965

访问量：5665

签　名：

等　　级
排　　名	1511
经　　验	2825
参赛次数	0
文章发表	53
年　　龄	18
在职情况	学生
学　　校	南京工程学院
专　　业	软件工程

　　自我简介：

76_105_89_105_110_103

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (III) （C语言代码）

1501: 蓝桥杯算法提高VIP-分苹果（c++版）运用差分数组降低时间复杂度

　　作者: Luftmensch　　　　发表时间：2022-02-18 14:01:57 浏览：286　|　评论：0　

原题链接：蓝桥杯算法提高VIP-分苹果

:tw-2600:**解题思路：**
题目中m n数据量达是1e5限时1sec显然暴力枚举会超时，因此我们就需要使用到**差分数组**，这样可以**降低时间复杂度**
**关于差分数组，如果你想对第i位到j位进行加一操作，你只需要将差分数组第i位+1，第j+1位-1，然后对每一项求前缀和即可推出原数组进行相关操作后的结果了，具体操作见以下代码**
:tw-2705:具体代码：
```cpp
#include<iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int differ[100005] = { 0 };
    for (int i = 0; i < m; i++)
    {
        int l, r, c;
        cin >> l >> r >> c;
        differ[l] += c;
        differ[r + 1] -= c;

}
    for (int i = 1; i <=n; i++)
    {
        differ[i] += differ[i - 1];
        cout << differ[i] << " ";
    }
    cout << endl;
    return 0;
}
```
补充：对于m n小的时候可以采取这种简单方法，但是题目中m n可达1e5，如果再采取这种方法显然时间复杂度太大，栈堆容易爆掉或者超时
:tw-274e:错误代码：
```cpp
#include<iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int arr[100000] = { 0 };
    for (int i = 0; i < m; i++)
    {
        int l, r, c;
        cin >> l >> r >> c;
        for (int j = l - 1; j <= r - 1; j++)
            arr[j] += c;     
    }
    for (int i = 0; i <n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}
```
 :tw-3299:补充：如果初始arr[]状态要输入，不是000可以这样写
```cpp
#include<iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int arr[1000] = { 0 };
    for (int i = 1; i <=n; i++)
        cin >> arr[i];
    int dif[1000] = { 0 };
    for (int i = 1; i <= n; i++)
        dif[i] = arr[i] - arr[i - 1];
    for (int i = 0; i < m; i++)
    {
         int l, r, c;
         cin >> l >> r >> c;
         dif[l] += c;
         dif[r + 1] -= c;      
    }
      for (int i = 1; i <=n; i++)
      {
          arr[i] = dif[i] + arr[i - 1];//注意不是dif[i-1]
          cout << arr[i] << " ";
      }
            cout << endl;
    return 0;
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Luftmensch

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

矩形面积交（C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

剪刀石头布（C语言代码）

1501: 蓝桥杯算法提高VIP-分苹果（c++版）运用差分数组降低时间复杂度

评论区

精彩推荐

用筛法求之N内的素数。（C++代码）

1013题解

1025题解

A+B for Input-Output Practice (V) （C语言代码）

简单的a+b （C语言代码）

Tom数（C语言代码）

IP判断（C语言代码）

Tom数（C语言代码）

数列排序（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

Luftmensch

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

矩形面积交 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

剪刀石头布 （C语言代码）

1501: 蓝桥杯算法提高VIP-分苹果（c++版）运用差分数组降低时间复杂度

评论区

精彩推荐

用筛法求之N内的素数。 （C++代码）

1013题解

1025题解

A+B for Input-Output Practice (V) （C语言代码）

简单的a+b （C语言代码）

Tom数 （C语言代码）

IP判断 （C语言代码）

Tom数 （C语言代码）

数列排序 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

矩形面积交（C语言代码）

剪刀石头布（C语言代码）

　　评论区

用筛法求之N内的素数。（C++代码）

Tom数（C语言代码）

IP判断（C语言代码）

Tom数（C语言代码）

数列排序（C语言代码）