题解 P4105 【[HEOI2014]南园满地堆轻絮 】

· · 题解

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

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

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

#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)快！！！