#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int a[N],b[N];//a原数组，b差分数组 
int n,p;
void insert(int l,int r,int v)
{
	b[l] = b[l] + v;
	b[r+1] = b[r+1] - v; 
}
int main() 
{
	cin>>n>>p;
	for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
	//求a数组的差分数组 
	for(int i = 1;i <= n;i++) insert(i,i,a[i]);
	//p次加分
	int l,r,v;
	for(int i = 1;i <= p;i++)
    {
		scanf("%d%d%d",&l,&r,&v);
		insert(l,r,v);
	} 
	//求每个人的分数
	int mi = INT_MAX;
	for(int i = 1;i <= n;i++)
    {
		b[i] = b[i] + b[i-1];
		mi = min(mi,b[i]);
	} 
	cout<<mi;
	return 0;
}

本题是一道经典的前缀和-差分问题，但千万不要强行枚举(O(n^2)的时间复杂度会TLE)。

//时间复杂度:O(N+M)
//主体部分
int main()
{
    cin>>n>>p;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];//初始化数组
    }
    for (int i=1;i<=n;i++)
    {
        b[i] = a[i] - a[i-1];//差分
    }
    while (p--)
    {
        cin>>l>>r>>c;
        b[l] += c;
        b[r+1] -= c;
    }
    for (int i=1;i<=n;i++)
    {
        b[i] += b[i-1];//prefix求前缀和
    }
    int min_num=1000000;//AC过，保证不会大于
    for (int i = 1;i<=n;i++)
    {
        (b[i]<min_num) ? min_num = b[i] : min_num+=0;
    }

    cout<<min_num;
}

Loading:21/100……