A. Rooms and Passages

古城微笑少年丶 2022-10-18 15:59 82阅读 0赞

## 题目大意 ##

n+1个地牢，编号从0到n，其中有n个通道，编号从1到n；  
每个通道一个锁，每种锁有正负两种，正的可以多次通过，负的通过一次后，这种锁失效。  
问在房间s内，拥有所有种类的所，最多能到达几个房间。  
 0 < = s < = n − 1 0 <= s <= n-1 0<=s<=n−1

--------------------

## 题解 ##

从后往前遍历，如果是正数，后面的数值+1，记录对应通行证的最新位置  
如果是负数，判断后面是否出现，如果没有出现，+1；如果出现了，计算位置差。

--------------------

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    const int inf = 1e9+7;
    const int N = 5e5+5;
    int arr[N], pos[N], ans[N];
    
     void solve()
     { 
        int n;
        scanf("%d",&n);
        rep(i,0,n-1)
            scanf("%d",&arr[i]);
        int tmp = inf;
        fep(i,0,n-1)
         { 
            if(arr[i]>0)
            { 
                ans[i] = ans[i+1]+1;
                pos[arr[i]] = i; // 记录最新出现的位置
            }
            else // 为负数的情况
            { 
                if(!pos[-arr[i]]) ans[i] = ans[i+1] + 1; // 如果后面没有
                else{ 
                    tmp = min(tmp,pos[-arr[i]]);
                    ans[i] = tmp - i;
                }
            }
        }
         rep(i,0,n-1) printf("%d%c",ans[i],i==n-1?'\n':' ');
        
     }
     
     
    int main() { 
        solve();
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，82人围观）

还没有评论，来说两句吧...

相关阅读

相关【英语学习】【Level 07】U04 Rest and Relaxation L4 A room fit for a king

文章目录 Word Preparation suite: 套房 decor: 装潢 well-maintained: 维护良

淡淡的烟草味﹌/ 2023年10月11日 12:16/ 0 赞/ 47 阅读

相关 English trip EM3 LP4A ROOMS Teacher:Lamb

课上内容（Lesson）词汇（Key Word ） \ rooms living room dining room kitchen bedroom

港控/mmm°/ 2023年06月01日 06:29/ 0 赞/ 8 阅读

相关 A. Rooms and Passages

题目大意 n+1个地牢，编号从0到n，其中有n个通道，编号从1到n；每个通道一个锁，每种锁有正负两种，正的可以多次通过，负的通过一次后，这种锁失效。问在房间s

古城微笑少年丶/ 2022年10月18日 15:59/ 0 赞/ 83 阅读

相关题目217 a letter and a number

![20160729133037857][] 已AC代码： include<cstdio> using namespace std; in

不念不忘少年蓝@/ 2022年09月24日 11:15/ 0 赞/ 146 阅读

相关 NYOJ 217 a letter and a number

a letter and a number 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述 we define f(A) = 1,

刺骨的言语ヽ痛彻心扉/ 2022年08月25日 00:29/ 0 赞/ 169 阅读

相关 Difference between new A and new A()

问题： A是一个类，我们经常new一个A的对象，你经常会这么写： A pa = new A(); 但是如果我这么写呢： A pa = new A;

柔光的暖阳◎/ 2022年08月22日 13:28/ 0 赞/ 241 阅读

相关 const int a and int const a and const int * const a

关键问题点：const 属于修饰符，关键是看const 修饰的位置在那里 1、const int \a 这里const 修饰的是int，而int定义的是一个整值

你的名字/ 2022年08月20日 13:25/ 0 赞/ 183 阅读

相关 hdoj 4923 Room and Moor

题目：[hdoj 4923 Room and Moor ][hdoj 4923 Room and Moor] 来源：[2014 Multi-University T

川长思鸟来/ 2022年08月10日 17:50/ 0 赞/ 102 阅读

相关 CodeForces - 467A - A. George and Accommodation

-------------------- 题目连接：http://codeforces.com/problemset/problem/467/A 题目描述 Desc

た入场券/ 2022年06月12日 07:18/ 0 赞/ 199 阅读

相关 1097A Gennady and a Card Game

A. Gennady and a Card Game time limit per test 1 second memory limit per test 256 me

谁借莪１个温暖的怀抱￠/ 2022年03月30日 09:08/ 0 赞/ 144 阅读