思路就是暴力模拟,但有 3 个点 WA 了,求大佬指正 QwQ
#include <bits/stdc++.h>
using namespace std;
int n, w, a[100100], b[100100], ans = INT_MAX, cnt[100100];
int main() {
scanf("%d%d", &n, &w);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
++cnt[a[i]];
}
if (n == 1) {
puts("0");
return 0;
}
int diff = a[1] - a[0];
bool flag = 1;
for (int i = 2; i < n; ++i) {
if ((a[i] - a[i - 1]) != diff) {
flag = 0;
break;
}
}
if (flag && diff >= 0) {
puts("0");
return 0;
}
int maxcnt = 0;
for (int i = 0; i < n; ++i) {
maxcnt = max(maxcnt, cnt[a[i]]);
}
ans = n - maxcnt;
for (int i = 1; i <= ceil(w / double(n - 1)); ++i) {
int op = 0;
flag = 1;
memcpy(b, a, sizeof(a));
for (int j = 1; j < n; ++j) {
if ((b[j] - b[j - 1]) != i) {
b[j] = b[j - 1] + i;
if (b[j] > w) {
flag = 0;
break;
}
++op;
}
}
if (flag) {
ans = min(ans, op);
}
}
printf("%d", ans);
return 0;
}