牛客 黑龙江大学程序设计竞赛重现 19-4-25 D

题意: n项工作 1~n  工时s[i] ~e[i]， 工时有覆盖的工作不能被同一台机器同时操作， 问完成所有工作的最少机器数

思路：前缀差分和

e.g.

a            2 3 4              machine 2

b         1 2 3                 machine1

c                     5 6 7     machine2    a做完后空闲做c

d               3 4 5 6 7     machine1    b做完后空闲做d

最少两台机器

计算时间段重叠，时间点不计

则标记 a[ s[i] ]++, a[ e[i] ]--  （若计时间点则 a[ e[i]+1 ]--

计算前缀和  最大值即为最少机器数

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<string>

#include<algorithm>

#include<map>

#include<queue>

#include<stack>

#include<list>

#include<set>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> p;

typedef long double ld;

#define mem(x) memset(x, 0, sizeof(x))

#define me(x) memset(x, -1, sizeof(x))

#define fo(i,n) for(i=0; i<n; i++)

#define sc(x) scanf("%lf", &x)

#define pr(x) printf("%lld\n", x)

#define pri(x) printf("%lld ", x)

#define lowbit(x) x&-x

const ll MOD = 1e18 +;

const ll N = 6e6 +;

ll a[N], s[N];

int main()

{

    ll i, j, k, l=;

    ll n, m=, t;

    cin>>n;

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

    {

        cin>>k>>t;

        a[k]++;

        a[t]--;

        m=max(m,t+);

    }

    k=;

    s[]=a[];

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

    {

        s[i]=s[i-]+a[i];

        k=max(k,s[i]);

        cout<<s[i]<<' ';

    }

    cout<<endl;

    cout<<k<<endl;

    return ;

}