自动搬运

查看原文

来自洛谷，原作者为

	Ameyax **

搬运于2025-08-24 21:56:34，当前版本为作者最后更新于2018-01-15 21:13:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

贪心 我们需要把所有逆序对都变成非逆序的

那么就有一个显然的结论：答案就是差距最大的逆序对的一半

如果有更大的，那一定是你的最大逆序对找错了

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL n, sa, sb, sc, sd, a1, a2, ai, mod, maxn, ans;
LL F(LL x)
{
    LL x1 = (sa * x) % mod;
    x1 = (x1 * x) % mod;
    x1 = (x1 * x) % mod;
    LL x2 = (sb * x) % mod;
    x2 = (x2 * x) % mod;
    LL x3 = (sc * x) % mod;
    return (((((x1 + x2) % mod) + x3) % mod) + sd) % mod;
}
int main()
{
    cin >> n >> sa >> sb >> sc >> sd >> a1 >> mod;
    maxn = a1;
    for (int i = 2; i <= n; i++)
    {
        ai = F(a1) + F(a2);
        if (ai < mod) ai += mod;
        if (ai > mod) ai %= mod;
        if (maxn - ai > ans) ans = maxn - ai;
        if (ai > maxn) maxn = ai;
        a2 = a1; a1 = ai;
    }
    cout << (ans + 1) / 2 << endl;
    return 0;
}

另外还可以二分答案，check函数大概长这样

bool check(int x)
{
    int maxn = 1;
    for (int i = 1; i <= n; i++)
    {
        maxn = max(maxn, a[i] - x);
        if (maxn > a[i] + x)
            return 0;
    }
    return 1;
}

这里我还有一句话一定要说，我的$O(n)$算法没有我前面那位神犇的$O(nlogn)$快！！！