Algorithmic Crush

evendra在9号云上看到了他的教练朝他微笑。 每次教授选出Devendra单独问他一个问题，Devendra朦胧的头脑里全是他的教练和她的微笑，以至于他无法专注于其他事情。帮助他解决这个问题：



给你一个长度为N的列表，列表的初始值全是0。对此列表，你要进行M次查询，输出列表种最终N个值的最大值。对每次查询，给你的是3个整数——a,b和k，你要对列表中从位置a到位置b范围内的（包含a和b)的全部元素加上k。

输入格式



第一行包含两个整数 N和 M。

接下来 M行，每行包含3个整数 a, b 和 k。

列表中的数位置编号为从1到 N。

输出格式



单独的一行包含 最终列表里的最大值

约束条件



3 <= N <= 10^7

1 <= M <= 2*10^5

1 <= a <= b <= N

0 <= k <= 10^9

输入样例 #00:

5 3
1 2 100
2 5 100
3 4 100

输出样例 #00:

200

解释:

第一次更新后，列表变为 100 100 0 0 0，

第二次更新后，列表变为 100 200 100 100 100。

第三次更新后，列表变为 100 200 200 200 100。

因此要求的答案是200。

前缀和思想

#include<bits/stdc++.h>
using namespace std;
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int n,q,x,y;
    long long k;
    cin>>n>>q;
    vector<int>a(n+1);
    for(int i=1;i<=q;i++){
        cin>>x>>y>>k;
        a[x]+=k;
        a[y+1]-=k;
    }
    long long Max=0;
    long long sum=0;
    for(int i=1;i<=n;i++){
      sum+=a[i];
      Max=max(sum,Max);
    }
    cout<<Max<<endl;
    return 0;
}

原文链接: https://www.cnblogs.com/pk28/p/6554618.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍