3 条题解

  • 5
    @ 2023-12-19 13:12:54

    感谢同学用户 - 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;
    }
    

    信息

    ID
    965
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    708
    已通过
    66
    上传者