Description

给定一个整数数列 a,定义 ,保证 f(a)>0f(a) > 0 你需要求出至少需要修改 a 的多少个位置才能使f(a) f(a)变小。注意,你修改之后的数也必须是整数。

Hint

Solution

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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;
}