Problem4.30 数列(sequence)

4.30 数列(sequence)

Description

给定一个整数数列 a,定义f(a) = max_{1\leq i < j \leq n} \{ a_j-a_i \},保证 f(a) > 0
你需要求出至少需要修改 a 的多少个位置才能使 f(a)变小。注意,你修改之后的数也必须是整数。

Hint

2 \leq n \leq 10^6 , |a_i| \leq 10^9

Solution

这道题刚看起来没有一点思路,感觉完全不知道怎么做。仔细分析之后就可以发现实际上就是一个简单的贪心。我们先将最大的符合条件的差值Max求出,然后再扫一遍,将所有满足差值为Max的这样的组合找出,把数量直接加起来即可

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 2 * 1e6 + 100;

int N, A[Maxn], P[Maxn];

int maxx = -0x3f3f3f3f, ans = 0x3f3f3f3f;

inline void Check (int sum)
{
    int Min = 0x3f3f3f3f, Max = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (!P[i])
        {
            Min = min(Min, A[i]);
            Max = max(Max, A[i] - Min);
        }
    }
    if (Max < maxx)
    {
        ans = min(ans, sum);
    }
}

inline void dfs (int x, int sum)
{
    if (x == N)
    {
        Check(sum);
        return ;
    }
    P[x + 1] = 1;
    dfs(x + 1, sum + 1);
    P[x + 1] = 0;
    dfs(x + 1, sum);
}

map <int, int> Map;
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    scanf("%d", &N);

    int Max = -0x3f3f3f3f, Min = INT_MAX, top = 0;
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &A[i]);
        Min = min(Min, A[i]);
        Max = max(Max, A[i] - Min);
    }
    if (N <= 20)
    {
        maxx = Max;
        dfs(0, 0);
        cout<<ans<<endl;
        return 0;
    }

    int Ans = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (Map[A[i] - Max])
        {
            Map[A[i] - Max] --;
            ++Ans;
        }
        Map[A[i]]++;
    }
    cout<<Ans<<endl;
    return 0;
}

Categories: Problem Tags:

Comments

No Comments Yet. Be the first?

Post a comment