题解 P1083 【借教室】

noble_ · 2018-06-18 16:01:03 · 题解

无耻的安利一发自己博客：传送门

哈哈哈哈，蒟蒻来介绍一种暴力新做法

这题前缀和搞一搞是可以把每天的教室需求数量算出来的

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

代码：

#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行！！！！