有个疑问
查看原帖
有个疑问
895690
gghack_Nythix楼主2023/6/29 20:28

此代码的二分为什么 + 1才能100分,而不+ 1只有5分

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c[2000005],d[2000005],s[2000005],t[2000005],_q[2000005],__q[2000005],n,m;
bool check(int x){
	memset(_q,0,sizeof(_q));
	for(int i = 1;i <= x;++i){
		_q[s[i]] += d[i];
		_q[t[i] + 1] -= d[i];
	}
	for(int i = 1;i <= n;++i){
		__q[i] = __q[i - 1] + _q[i];
		if(__q[i] > c[i]){
			return 0;
		}
	}
	return 1;
}
signed main(){
	cin >> n >> m;
	for(int i = 1;i <= n;++i){
		cin >> c[i];
	}
	for(int i = 1;i <= m;++i){
		cin >> d[i] >> s[i] >> t[i];
	}
	int l = 1,r = m,ans = 0;
	if(check(m)){
		cout << 0 << endl;
		return 0;
	}
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			ans = mid;
			l = mid + 1;
		}
		else{
			r = mid - 1;
		}
	}
	cout << -1 << endl << ans + 1 << endl;
}
2023/6/29 20:28
加载中...