2020-01-30
题目传送门：https://www.luogu.com.cn/problem/P1083
这道题是前几天那课上老师讲的题目，我大概理解了老师的意思，其实如果暴力的
写题目的话会超时，我今天正好有复习了已经忘了的差分和前缀和，差分实质上就
是前缀和求逆的过程，差分后的序列加上前缀和的序列最后等于原序列，差分的首
和末尾+1的数字进行相反的运算操作。
第一次写完的结果，不知道为什么连一半的数据都没过。
进行了无脑debug的模式，最后想了半个小时，发现自己的算法什么的没有问题啊，
突然猛然一惊，原来数组的大小还是上一道题目的数组的大小，我去，数组开小了！
当时记得以前也这样过，唉，好无语，白白浪费了这段时间，好气啊，然后最后提
交了代码，终于a了。。。。对了，为了优化时间复杂度，我在主函数里加了二分，
不知道不写二分会不会tle。代码如下
#include<iostream> #include<bits/stdc++.h> using namespace std; int n,m; int diff[1000100],need[1001000],rest[1000100],r[1000100],l[1000100],d[1000100]; bool wyq(int x){ memset(diff,0,sizeof(diff)); for(int i=1;i<=x;i++){ diff[l[i]]+=d[i]; //差分，序列的头部 diff[r[i]+1]-=d[i];//差分，序列的尾部+1 } for(int i=1;i<=n;i++){ need[i]=need[i-1]+diff[i];//求原序列 if(need[i]>rest[i]) return 0; } return 1; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>rest[i]; for(int i=1;i<=m;i++) cin>>d[i]>>l[i]>>r[i]; if(wyq(m)){ cout<<"0"; return 0; } int x=1,y=m; while(x<y){ int mid=(x+y)/2; if(wyq(mid)) x=mid+1; else y=mid; } cout<<"-1"<<endl<<y; return 0; }
这道题大佬们感觉可能比较水吧，但是我又拿这道题重新温习了一下
以前忘记的知识，希望这个集训对我来说有所收获吧！！！加油呀！
原文：https://www.cnblogs.com/ssxzwwsjz/p/12243347.html