CF - 803B. Distances to Zero - 栈模拟

xiaoxiao2021-02-27  546

题目描述: B. Distances to Zero time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

You are given the array of integer numbers a0, a1, ..., an - 1. For each element find the distance to the nearest zero (to the element which equals to zero). There is at least one zero element in the given array.

Input

The first line contains integer n (1 ≤ n ≤ 2·105) — length of the array a. The second line contains integer elements of the array separated by single spaces ( - 109 ≤ ai ≤ 109).

Output

Print the sequence d0, d1, ..., dn - 1, where di is the difference of indices between i and nearest j such that aj = 0. It is possible that i = j.

Examples input 9 2 1 0 3 0 0 3 2 4 output 2 1 0 1 0 0 1 2 3 input 5 0 1 2 3 4 output 0 1 2 3 4 input 7 5 6 0 1 -2 3 4 output 2 1 0 1 2 3 4 题意概述:给你n个数组,要你求对于每个数a[i]问它到周围第j个数a[j]且a[j]等于0的距离的最小值。题目保证有解。解题思路:最开始想法是暴力,对于每个元素向左向右延伸一遍更新最小值,成功T了。然后想怎么简化,实际上对于每次出现的0,正着更新一下它左边的非零数的坐标,再倒着更新一下它右边非0数的坐标取最小值即可。具体实现可以用一个栈存下标,如果当前数不是0则入栈,否则把栈内弹出,对于每个栈顶元素它到这个0的距离就是i - top。AC代码: #include <bits/stdc++.h> #define INF 0x3f3f3f3f #define maxn 200100 #define lson root << 1 #define rson root << 1 | 1 #define lent (t[root].r - t[root].l + 1) #define lenl (t[lson].r - t[lson].l + 1) #define lenr (t[rson].r - t[rson].l + 1) #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; typedef unsigned long long ull; int a[maxn], d[maxn]; stack<int> s; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif int n; while (~scanf("%d", &n)) { fill(d, d + n + 1, INF); while (!s.empty()) s.pop(); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (a[i] == 0) { d[i] = 0; while (!s.empty()) { int cur = s.top(); s.pop(); d[cur] =min(d[cur], i - cur); } } else s.push(i); } while (!s.empty()) s.pop(); for (int i = n; i > 0; i--) { if (a[i] == 0) { while (!s.empty()) { int cur = s.top(); s.pop(); d[cur] = min(d[cur], cur - i); } } else s.push(i); } for (int i = 1; i <= n; i++) if (i == 1) printf("%d", d[i]); else printf(" %d", d[i]); puts(""); } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }
转载请注明原文地址: https://www.6miu.com/read-384.html

最新回复(0)