BUPT 2017 summer training (for 16) #1F
模拟,先看从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;
}