BZOJ1811 [IOI2005]mea

2015.01.16 08:20 Fri| 4 visits oi_2015| 2015_刷题日常| Text

Sulution

mea,顾名思义,是 mean sequence 的意思。

由题意易得,若 $a_1$ 确定,则数列中各项的值均确定。将每一项的值用 $a_1$ 表示,得到如下形式

又由 $a_1 \le m_1 \le a_2 \le m_2 \le a_3 \le m_3 \le \cdots$ ,可解出 $a_1$ 的上界和下界。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 5000005
#define inf 0x7fffffffffffffffLL

int n;
long long m, s, maxa = inf, mina = -inf;

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        m = read();
        s = 2 * m - s;
        if (i & 1)
            maxa = min(maxa, s - m);
        else
            mina = max(mina, m - s);
    }
    cout << max(0LL, maxa - mina + 1) << endl;
}