题解 P1083 【借教室】
noble_
2018-06-18 16:01:03
无耻的安利一发自己博客：[传送门](http://www.cnblogs.com/noblex/)
---
哈哈哈哈，蒟蒻来介绍一种暴力**新**做法
这题前缀和搞一搞是可以把每天的教室需求数量算出来的
```cpp
sum[s[i]]+=d[i]; sum[t[i]+1]-=d[i];
........
........
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
```
这样子就把每天的需求量统计出来了
接着一个循环暴力计算哪天供不应求，再暴力一个个减回去直到符合条件
最坏复杂度是可以卡到$ O(mn) $的，但可能出题人去卡其他做法了QwQ
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
int s[maxn],t[maxn];
long long sum[maxn],r[maxn],d[maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&r[i]);
for(int i=1;i<=m;i++){
scanf("%lld%d%d",&d[i],&s[i],&t[i]);
sum[s[i]]+=d[i]; sum[t[i]+1]-=d[i];
}
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
int anss=1e9;
for(int i=1;i<=n;i++){
if(sum[i]>r[i]){
long long ans=sum[i]; int j;
for(j=m;j>=1;j--){
if(s[j]<=i && t[j]>=i){
ans-=d[j]; if(ans<=r[i]) break;
}
}
anss=min(anss,j);
if(anss==1) break;
}
}
if(anss==1e9) puts("0");
else printf("%d\n%d",-1,anss);
return 0;
}
```
没读入优化1120ms
这种小优化暴力真是NOIp中的不二之选啊，代码只有31行！！！！