根据y总代码以及网友对y总代码解析编写
#include<iostream>
#include<algorithm>
using namespace std;
long int r[1000010],d[1000010],s[1000010],t[1000010],c[1000010];
long int n,m,i,x,y,z,j=1;
bool chazhao(int k)
{
for(i=1;i<=n;i++)
c[i]=r[i];//拷贝r[i]防止更改r[i]
//以下是在左支查看是否有爆掉的(方法是主函数中的例子)
for(i=1;i<=k;i++)
{
c[s[i]]-=d[i];
c[t[i]+1]+=d[i];
}
for(i=1;i<=n;i++)
{
c[i]+=c[i-1];
if(c[i]<0)
return false;//爆掉返回false回主函数在左支二分
}
return true;//否则返回true回主函数在右支二分
}
int main()
{
cin>>n>>m;//输入天数和订单数量
for(i=1;i<=n;i++)
cin>>r[i];//每天可提供教室数量
for(i=1;i<=m;i++)
cin>>d[i]>>s[i]>>t[i];//分别输入每个订单的天数,起始时间,终止时间
for(i=n;i>0;i--)
r[i]=r[i]-r[i-1];//从最后一个数字(每天可提供教室数量)开始减去前一天可提供教室数
/*这样的话如果想要算出每个订单完成之后每个教室剩余数量,只需将起始时间的r[s[i]]减去订单需求教室数,
将结束时间的下一位r[t[i]+订单需求教室数],最后从r[i]的第二个数开始每个数加上前一位r[i-1]即可
举个例子
n=5,m=3;
每天可提供教室数量:4,6,3,2,7
单1:2 2 4
单2:3 1 3
单3:1 3 5
常规来说我们先看单一从第二天循环到第四天(循环3次)每天可提供教室数量减2得:
4,4,1,0,7
再看单二从第一天循环到第三天(循环3次)每天可提供教室数量减3得:
1,1,-2,0,7
最后看单三从第三天循环到第五天(循环3次)每天可提供教室数量减1得:
1,1,-3,-1,6
现在我们用上述做法
首先处理每天可提供教室数量(从最后一个数字(每天可提供教室数量)开始减去前一天可提供教室数)得:
4,2,-3,-1,5
单一
第二天对应r[2]-2,第四天的下一位r[5]+2,得:
4,0,-3,-1,7
单二
1,0,-3,2,7
单三:
1,0,-4,2,7,1
从r[i]的第二个数开始每个数加上前一位r[i-1]得:
1,(1+0),(-4+1),(2+-3),(7+-1);(超出部分(1)不用管)
1,1,-3,-1,6
最后结果和我们第一次做法结果一样,并且减少了循环次数
*/
x=0;
y=m+1;//双指针指向订单头和订单末尾
while(x+1!=y)//满足的话说明二分查找结束(二分查找的目的是找到第一个爆掉的订单或者全部满足)
{
if(chazhao((x+y)/2))
{
x=(x+y)/2;
}
else
y=(x+y)/2;
}
if(x==m)
cout<<0;
else
cout<<-1<<endl<<y;
}
以上文字是本人对代码理解,由于本人之前没学过差分,如果理解有误,望指出,多谢!