AtCoder Caddi 2018 E. Negative Doubling (Stack)

日付: 12月 23, 2018

[E - Negative Doubling](https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c)
## Problem
Given an array of $n$ positive numbers, you can choose a number and multiply it by -2. Calculate the minimum possible number of operations to make the array non-decreasing.

**Constraints:** $1\le n \le 2\cdot 10^5,\ 1 \le A_i \le 10^9$

## Solution
If we perform the optimal strategy, at least one of the numbers does not change, and all numbers after it is positive, all numbers before it is negative. We define two arrays $L$ and $R$. $L_i$ is the minimum number of operations needed to make numbers before $A_i$ (inclusively) **non-increasing**. $R_i$ is the minimum number of operations needed to make numbers after $A_{n+1-i}$ (inclusively) **non-decreasing**. We can calculate $L$ and then reverse $A$ and calculate $R$. If $L$ and $R$ is calculated, answer is $min\{L_{i-1} + i-1 + R_{n+1-i}\}$.

To calculate $L$,  iterating $i$, if $A_i > A_{i-1}$, we must multiply $A_{x\cdots i-1}$ by 4 until $A_{i-1} \ge A_i$. But $x$ is not known, we can maintain a stack such that its top is always $x-1$. If $A_{i-1} \ge 4A_i$, $i-1$ will not be used. So if $A{i-1} \ge 4A_i$, we can calculate after how many operations of multiplying $A_i$ by 4, this condition is hold, and push $i-1$ into the stack for that number of times.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

const int N = 2e5 + 5;
int n, A[N], S[N * 3];
LL L[N], R[N];

void calc(LL *F) {
    for (*S = 0; *S < n;) S[++*S] = 0;
    LL sum = 0;
    FI(i, 2, n) {
        LL x = A[i - 1], y = A[i];
        while (x < y) sum += i - 1 - S[(*S)--], x *= 4;
        while (x >= y * 4) S[++(*S)] = i - 1, y *= 4;
        F[i] = sum * 2;
    }
}

int main() {
    scanf("%d", &n);
    FI(i, 1, n) scanf("%d", A + i);
    calc(L), reverse(A + 1, A + 1 + n), calc(R);
    LL ans = LLONG_MAX;
    FI(i, 1, n) ans = min(ans, L[i - 1] + i - 1 + R[n - i + 1]);
    printf("%lld\n", ans);
}
```

KONGROOの基地

このブログを検索

AtCoder Caddi 2018 E. Negative Doubling (Stack)

コメント

コメントを投稿