读完题目我们大概就可以想到一种暴力解法了
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N=1e6+5; int sum[N],d,r[N],s,t,n,m; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&r[i]); for(int i=1;i<=m;i++) { scanf("%d%d%d",&d,&s,&t); for(int j=s;j<=t;j++) { sum[j]=sum[j]+d; if(r[j]<sum[j]) { cout<<"-1"<<endl<<i; return 0; } } } cout<<"0"; return 0; }
要是能在考场上混45分,那还是不错的。
差分数组
设一个数组diff【】。
那么什么是差分数组呢:
用diff[ i ]记录当前项与上一项的差值:diff[ i ]=a[ i ]-a[ i-1 ];
所以如果我们知道diff【0...i】,就可以求出a【i】了
它的厉害之处在于哪里呢?
如果我们要让a[ l ],a[ l+1 ]...a[ r ]的值同时加上或减去一个数,那么可以这么做
diff[ l ]+=x;
diff[ r+1 ]-=x;
因为对于这个数列,只有两处相邻差发生改变。所以可以O(1)地修改。
对于这道题
如果要检查第一份到第 i 份订单是否有需要修改的,
那么就这么就根据上面说的方法,把d[ 1 ]到d[ i ]一个个加到相应的区间上。
bool check(int per) { memset(diff,0,sizeof(diff)); for(int i=1;i<=per;i++) { diff[s[i]]+=d[i]; diff[t[i]+1]-=d[i]; } for(int i=1;i<=n;i++) { need[i]=need[i-1]+diff[i]; if(need[i]>r[i]) return true; } return false; }
所以我们就从1到n跑一遍check就可以了对不对?
别急,先看看能不能二分。
这道题里,如果第 i 份订单需要修改,后面的订单也无法满足。满足单调性。
那么就可以二分了,节约大把时间。
while(l<=r) { mid=(l+r)>>1; if(check(mid))//找到一个可行解,保存下来,看看有没有更优的(更靠前 { ans=mid; r=mid-1; } else l=mid+1; }
本文结束,谢谢大佬
顾z 的个人中心 - 洛谷 | 计算机科学教育新生态
https://www.luogu.org/user/87960
_皎月半洒花 的个人中心 - 洛谷 | 计算机科学教育新生态
https://www.luogu.org/user/28313