NOIP2012D2T2 借教室

wjh15101051's space

卧薪尝胆，厚积薄发。

NOIP2012D2T2 借教室

Date: Thu Sep 06 00:35:45 CST 2018

In Category: NoCategory

Description：

第 $i$ 天有 $k_i$ 个教室可借，第 $j$ 个请求形如在 $l_j$ 和 $r_j$ 借 $s_j$ 个教室，问第一个不满足的请求。

$1\le n \le 10^6$

Solution：

先二分一个值，然后差分，前缀和判断即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1000010

int p[MAXN];

inline int read()

{

    register int res = 0;

    register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int s[MAXN],l[MAXN],r[MAXN];

int c[MAXN];

bool check(int k)

{

    memset(c,0,sizeof(c));

    for(int i = 1;i <= k;++i)

    {

        c[l[i]] -= s[i];

        c[r[i] + 1] += s[i];

    }

    for(int i = 1;i <= n;++i)

    {

        c[i] += c[i - 1];

        if(c[i] + p[i] < 0)return false;

    }

    return true;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)p[i] = read();

    for(int i = 1;i <= m;++i)

    {

        scanf("%d%d%d",&s[i],&l[i],&r[i]);

    }

    int l = 0,r = m,mid;

    while(l < r)

    {

        mid = ((l + r + 1) >> 1);

        if(check(mid))l = mid;

        else r = mid - 1;

    }

    if(l == m)puts("0");

    else

    {

        puts("-1");

        cout << l + 1 << endl;

    }

    return 0;

}

In tag: 算法-二分算法-差分

wjh15101051