算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1E6 +11;
ll n, m, su[N], d[N], s[N], t[N], diff[N];
bool check(int x){
memset(diff, 0, sizeof(diff));
for(int i = 1; i <= x; ++ i){//前x项差分操作
diff[s[i]] += d[i];
diff[t[i] + 1] -= d[i];
}
for(int i = 1; i <= n; ++ i){//对全n项前缀和!!
diff[i] += diff[i - 1];
if(diff[i] > su[i]) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> su[i];
for(int i = 1; i <= m; ++ i) cin >> d[i] >> s[i] >> t[i];
int l = 0, r = m, mid;
while(l < r){//因为当l=r时,区间内只有一个值记为答案
//多个订单随机挑选一个中间,看从1到mid的差分前缀和
mid = l + r >> 1; //下取整
if(check(mid)) l = mid + 1;//左半部分都是可以的
else r = mid;//只要有非法值r就会左移
//printf("%d% d %d\n", mid, l, r);
}
if(check(l)) cout << 0;
else cout << -1 << '\n' << r;
return 0;
}
算法2
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1E6 +11;
ll n, m, su[N], d[N], s[N], t[N], diff[N];
bool check(int x){
memset(diff, 0, sizeof(diff));
for(int i = 1; i <= x; ++ i){//前x项差分操作
diff[s[i]] += d[i];
diff[t[i] + 1] -= d[i];
}
for(int i = 1; i <= n; ++ i){//对全n项前缀和!!
diff[i] += diff[i - 1];
if(diff[i] > su[i]) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> su[i];
for(int i = 1; i <= m; ++ i) cin >> d[i] >> s[i] >> t[i];
int l = 0, r = m, mid;
while(l < r){
//多个订单随机挑选一个中间,看从1到mid的差分前缀和
mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;//只要有非法值r就会左移,最后查找到那个非法值的-1位
//printf("%d% d %d\n", mid, l, r);
}
if(r == m) cout << 0;
else cout << -1 << '\n' << r + 1;
return 0;
}