感谢同学用户 - 2315 - 南阳理工学院OJ (fuquan.moe)

using namespace std;
const int N = 1e5 + 10;
long long arr[N], brr[N],l[N],r[N],x[N],n,m;
int axx(int c)//差分
{
	brr[1] = m;
	for (int i = 2; i <= n; i++)
		brr[i] = 0;
	for (int i = 1; i <= c; i++)
	{
		brr[l[i]] -= x[i];
		brr[r[i] + 1] += x[i];
	}
	for (int i = 1; i <= n; i++)
	{
		arr[i] = arr[i - 1] + brr[i];
		if (arr[i] <= 0)return 1;
	}
	return 0;
}
int main()
{
	cin >> n >> m;
	brr[1] = m;
	for (int i = 1; i <= n; i++)
		cin >> l[i] >> r[i] >> x[i];
	int i = 1, j = n;
	while (i < j)//二分时间，总共n秒
	{
		int mad = (i + j) / 2;
		if (axx(mad))j = mad;
		else
			i = mad + 1;
	}
	if (j == n)//特判j=n的情况
	{
		if (axx(n))cout << n;//如果炸断了就输出n
		else
			cout << "impossible";//如果n秒后炸不断，就输出impossible
	}
	else
		cout << j;
}

很明显这道题是一个差分题，但是要求我们判断断裂数组的最小时间，一个暴力的想法是每次都在轰炸的地方加上对应的杀伤力，如果有一个位置的杀伤力>=m,就输出对应的秒数，但是这种方法的时间复杂度为O(n^2),数据给的范围是1e5,我们可以想办法把他优化到O(nlogn)，不妨换个角度思考，从答案的角度来看，我们需要找到一个最小数，也就是说答案可以理解为是递增的，根据logn的复杂度我们可以想到二分查找，即对答案进行二分查找，这样我们二分答案然后差分数组，就能得到时间复杂度为O(nlogn)的算法。 代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxv=1e5+10;
#define ll long long
ll n,m,lefts[maxv],rights[maxv],values[maxv],arr[maxv]={0};
bool judge(int time){
	memset(arr,0,sizeof(arr));//重置数组值为0
	//此处差分为 
    for(int i=0;i<time;i++){
        arr[lefts[i]]+=values[i];
        arr[rights[i]+1]-=values[i];
    }
    ll maxv=*max_element(rights,rights+time);//找右边界最大值，缩短差分长度 
    //还原数组 
    for(int i=1;i<=maxv;i++){
        arr[i]+=arr[i-1];
        if(arr[i]>=m)return 1;//如果找到就返回true 
    }
    return 0;//否则返回false 
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>lefts[i]>>rights[i]>>values[i];
    }
    int l=0,r=n;
    //二分答案，此处为左闭右闭写法
	//int ans=0; 
    while(l<=r){
        int mid=l+(r-l)/2;
        if(judge(mid)){
        	//ans=mid若分不清l是答案还是r是答案可以再开一个ans记录 
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if(l<=n)cout<<l;//若没有找到那么l一定会越界 
    else cout<<"impossible";
	return 0;
}

时间复杂度O(nlogn); 空间复杂度O(n); 希望我的题解对你有帮助！

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<iomanip>
#include<cstring>
#include<ctime>
#include<unordered_map>
#include<stack>
#include<queue>
//*****************************************************************************************************************
//                .-~~~~~~~~~-._       _.-~~~~~~~~~-.
//            __.'              ~.   .~              `.__
//          .'//                  \./                  \\`.
//        .'//                     |                     \\`.
//      .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \\`.
//    .'//.-"                 `-.  |  .-'                 "-.\\`.
//  .'//______.============-..   \ | /   ..-============.______\\`.
//.'______________________________\|/______________________________`.
//*****************************************************************************************************************
using namespace std;
const int o = 1e7 + 10;
typedef pair<long, long>ll;
long long a[o], s[o], l1[o], r1[o], c1[o], t = 0;
void num(int l, int r, int c)
{
    a[l] -= c;
    a[r + 1] += c;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n, m;
    cin >> n >> m;
    long long l = 1, r = n;
    long long cmp = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> l1[i] >> r1[i] >> c1[i];
    }
    while (l <= r)
    {
        for (int i = 1; i <= n; i++)
        {
            s[i] = m;
            a[i] = s[i] - s[i - 1];
        }
        bool fg = 0;
        long long mid = l + r>> 1;
        for (int i = 1; i <= mid; i++)
        {
            num(l1[i], r1[i], c1[i]);
        }
        for (int i = 1; i <= n;i++)
        {
            s[i] = a[i] + s[i - 1];
            if (s[i]<= 0)
            {
                fg = 1;
            }
        }
        if (fg)
        {
            r = mid-1;
            cmp = mid;
        }
        else
        {
            l = mid+1;
        }
    }
    if (cmp!=0)
    {
        cout << cmp;
    }
    else
    {
        cout << "impossible";
    }
}