题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int n,m;
int w[N],l[N],r[N],d[N];
ll b[N];
bool check(int mid)
{
memset(b,0,sizeof b);
for(int i = 1; i <= mid; i ++ )
{
b[l[i]] += d[i];
b[r[i] + 1] -= d[i];
}
for(int i = 1;i <= n; i ++ )
{
b[i] += b[i - 1];
if(b[i] > w[i]) return false;
}
return true;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
cin >> w[i];
for(int i = 1; i <= m; i ++ )
cin >> d[i] >> l[i] >> r[i];
int l = 0,r = m;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
if(r == m)puts("0");
else printf("-1\n%d\n",r + 1);
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla