枚举公差，因为 $1 \le a_i \le w$，所以易得公差 $d \le \frac{w}{n}$。
接下来枚举数列的第一个数为 $k$，则我们可以表示出该数列的第 $i$ 项为 $k + d \times (i - 1)$。因为数列的项数与公差不变，即 $a_i$ 所对应的 $k$ 是唯一的(只有一个 $k$ 符合条件)，所以我们可以处理出当 $k$ 为第一项时，数列中有多少个数不需要被修改。根据刚刚表示的数列中第 $i$ 项的数，可以得到 $a_i$ 所对应的 $k$ 为 $a_i - d \times (i - 1)$。
一个需要注意的条件就是修改后每个数的范围是 $1 \le a_i \le w$，这个需要体现在你的程序中，同时还要注意一下数据类型(可能处理时会爆 int)。
最后给一个代码吧：
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const ll MAX = 3e5 + 5;
const ll MOD = 1e9 + 7;
ll read ();
ll a[MAX],b[MAX];
ll n,m,ans,num,s;
int main ()
{
n = read ();m = read ();
for (ll i = 1;i <= n;++i) a[i] = read ();
ans = n - 1;
for (int num = 0;num <= m / n;++num)
{
init (b);s = 0;
++b[a[1]];
for (ll i = 2;i <= n;++i)
{
ll tmp = a[i] - (i - 1) * num;
if (tmp <= 0 || tmp + (n - i) * num > m) continue;
++b[tmp];
s = max (b[tmp],s);
}
ans = min (ans,n - s);
}
printf ("%lld\n",ans);
return 0;
}
ll read ()
{
ll s = 0;ll f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
