专栏首页饶文津的专栏【CodeForces 730H】Car Repair Shop

【CodeForces 730H】Car Repair Shop

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【HDU 5438】Ponds

    存边的时候,要头尾都存这个边。用dfs或者队列删点,再用并查集或者dfs确定联通块,然后统计联通块的点数,最后累加。

    饶文津
  • 【UVALive - 6534 】Join two kingdoms (树的直径的期望)

    给两棵树,分别有 n,m 个节点(1 ≤ N, Q ≤ 4 × 10^4),等概率连接属于不同树的两个节点,求新树的直径(最远两点的距离)的期望。

    饶文津
  • 【hihocoder 1424】 Asa's Chess Problem(有源汇上下界网络流)

    饶文津
  • 数组的简单练习题

    1.将一个给定的整型数组转置输出, 例如: 源数组,1 2 3 4 5 6 转置之后的数组,6 5 4 3 2 1

    阮键
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • P1197 [JSOI2008]星球大战

    题目描述 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几...

    attack
  • 2016天梯模拟赛 进阶题解

    L2-005 集合相似度 题目链接: https://www.patest.cn/contests/gplt/L2-005 题目的意思是要求两个集合的交集中...

    ShenduCC
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • 洛谷P4054 [JSOI2009]计数问题(二维树状数组)

    attack

扫码关注云+社区

领取腾讯云代金券