BUPT 2017 summer training (for 16) #1F

题意

依次有n (1 ≤ n ≤ 200) 个车要修理，每个车希望在s[i]时刻开始修理，时长d[i]，如果s[i]后面没有那么多空的时间，那么就选最小的可行的起点。\(s_i, d_i (1 ≤ s_i ≤ 10^9, 1 ≤ d_i ≤ 5·10^6)\)

题解

模拟，先看从s[i]时刻开始修理，和之前i-1个是否冲突。如果冲突，就枚举每个s[j]+d[j]时刻开始，看是否冲突，再从中选择最小的时刻。

代码

#include <cstdio>

#include <algorithm>

#define N 201

#define inf 0x3f3f3f3f

using namespace std;

int n;

int s[N],d[N];

bool ck(int i,int j){

    return s[j]>s[i]+d[i]-1 || s[i]>s[j]+d[j]-1;

}

int main(){

    scanf("%d",&n);

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

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

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

        bool fromS=true;

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

            if(!ck(i,j))

                fromS=false;

        if(!fromS){

            int ss=inf;

            for(int j=0;j<i;++j){

                s[i]=s[j]+d[j]+(j==0);

                bool valid=true;

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

                    valid&=ck(i,k);

                if(valid) ss=min(s[i],ss);

            }

            s[i]=ss;

        }

        printf("%d %d\n",s[i],s[i]+d[i]-1);

    }

    return 0;

}