题意：有一些学（xian）生（quan）要借教室。在n天内，第i天学校有ri个教室。有m份订单，每份订单有三个数值dj，sj，tj，分别表示这个订单从第sj天开始到第tj天结束（包括端点），每天需要dj个教室。
我们要按照订单的顺序一次处理每一个订单，如果有某个订单不能满足（当天的教室数量小于需求数），就需要输出-1和这个订单的序号，否则输出0
首先看到这个题，第一想到的当然是暴力了qwq。依次处理每一个订单，暴力从每一天的教室数量内减去需求数，如果某一天教室数量小于0，就输出这份订单的编号
时间复杂度O(mn)
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int ans=0;
char last=' ',ch=getchar();
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
struct ding
{
int d,s,t;
}dan[1000005];
int n,m;
int r[1000005];
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) r[i]=read();
for(int i=1;i<=m;i++)
{
dan[i].d=read();
dan[i].s=read();
dan[i].t=read();
}
for(int i=1;i<=m;i++)
{
for(int j=dan[i].s;j<=dan[i].t;j++)
{
r[j]-=dan[i].d;
if(r[j]<0)
{
printf("-1\n%d",i);
return 0;
}
}
}
printf("0");
}
能拿45分。
开动你聪明的小脑袋想（tou）想（li），其实可以把每一个订单看成一个区间，那这个题不就是区间修改问题吗？于是我们很容易想到既好用又好写的线段树了。线段树操作方便，复杂度低，很适合做这道题
代码：
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<time.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
ll ans=0;
char last=' ',ch=getchar();
while(ch<'0' || ch>'9')last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
//head
哈哈哈没有想到吧这篇题解不是线段树
线段树什么的根本不存在的QωQ
咳咳咳。。。下面转入正题
我们可以用差分数组鸭。
对于一次从s开始到t，需要d的操作，我们只需要把差分数组的第s项-d，第t+1项+d就可以了。值得一提的是，负数显然不太好，所以我们可以把负数转化成正数然后比较大小
把差分数组的第s项+d，第t+1项-d
然后，对于这个神奇的答案范围，显然直接搞事情是不行的，我们可以二分，然后检查是否满足条件就可以了。
上海世界外国语中学初三某C姓同学的题解（正解）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000005
using namespace std;
int LEFT,MID,RIGHT,n,m,r[maxn],d[maxn],s[maxn],t[maxn],day[maxn];
bool judge(int mid)
{
memset(day,0,sizeof(day));
for (int i=1;i<=mid;i++)
{
day[s[i]]+=d[i];
day[t[i]+1]-=d[i];
}
if (day[1]>r[1])
return 1;
for (int i=2;i<=n;i++)
{
day[i]+=day[i-1];
if (day[i]>r[i])
return 1;
}
//cout << -1 << endl;
return 0;
}
int main()
{
//freopen("classroom.in","r",stdin);
//freopen("classroom.ans","w",stdout);
cin >> 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[i],&s[i],&t[i]);
LEFT=1;RIGHT=m;
while (LEFT<RIGHT)
{
MID=(LEFT+RIGHT)/2;
//cout << LEFT << " " << RIGHT << " " << MID << endl;
if (judge(MID))
RIGHT=MID;
else LEFT=MID+1;
}
if (m!=RIGHT)
{
cout << -1 << endl;
cout << RIGHT << endl;
}
else cout << 0 << endl;
return 0;
}
接下来是神（wai）奇（men）解（xie）法（dao）
这里我用了差分+前缀和的思想，把每一天需要的教室数量搞了出来，然后枚举每一天，直到发现供不应求的情况就滚回去一个个减，直到满足情况为止
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int ans=0;
char last=' ',ch=getchar();
while(ch<'0'||ch>'9') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
typedef long long ll;
struct ding
{
int d,s,t;
}dan[1000005];
int n,m;
int r[1000005];
int cf[1000005],sum[1000005];
int anss=2147483647;
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
r[i]=read();
}
for(int i=1;i<=m;i++)
{
dan[i].d=read();
dan[i].s=read();
dan[i].t=read();
sum[dan[i].s]+=dan[i].d;
//这里用了比较大小的方法,因为据说负数容易re
sum[dan[i].t+1]-=dan[i].d;
}
for(int i=1;i<=n;i++)
{
sum[i]+=sum[i-1];
}//计算每一天的教室需求量
for(int i=1;i<=n;i++)
{
if(sum[i]>r[i])//枚举到需求量大于拥有量
{
ll ans=sum[i];
int j;
for(j=m;j>=1;j--)
{
if(dan[j].s<=i&&dan[j].t>=i)
{
ans-=dan[j].d;
//暴力一个个减回去直到符合条件
if(ans<=r[i]) break;
}
}
anss=min(anss,j);//取最前面的
if(anss==1) break;
}
}
if(anss==2147483647) printf("0");
else printf("-1\n%d",anss);
return 0;
//最坏复杂度为O(mn)
}
理论上最坏复杂度是O(mn)的。。。但是实际跑起来还贼快，一定是随机数据的锅qwq