A. Desorting
Problem
Sol & Code
若序列一开始无序答案为 \(0\)
若有序即 \(a_1\leq a_2 \leq \dots \leq a_n\)。
若想让 \(a_i > a_j(i < j)\)，操作次数与两数差值 \(d(d = a_j - a_i)\) 相关为 \(\lfloor\dfrac{d}{2}\rfloor+1\)，差值越小操作次数越少，故枚举相邻两数取最少的操作次数。
时间复杂度为 \(O(n)\)
#include <bits/stdc++.h>
#define N 501
int T, n, a[N];
int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d", &T);
while (T--) {
int ans = 2147483647;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 2; i <= n; ++i) {
if (a[i] < a[i - 1]) { ans = 0; break; }
else ans = min(ans, (a[i] - a[i - 1]) / 2 + 1);
}
printf("%d\n", ans);
}
return 0;
}
B. Desorting
Problem
Sol & Code
设 \(x,y\) 是第 \(k\) 项为 \(n\) 的类斐波那契数列的前两项，有 \(F[k - 2]x+F[k - 1]y = n\)。
枚举 \(x\) 看是否存在合法的 \(y\)
时间复杂度为 \(O(n)\)
#include <bits/stdc++.h>
int T, n, k, f[31];
int main() {
f[0] = 1, f[1] = 1;
for (int i = 2; i <= 30; ++i) f[i] = f[i - 1] + f[i - 2];
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &k);
if (k >= 30) {puts("0"); continue; }
int ans = 0;
for (int i = 0; i <= n; ++i) {
if (((n - f[k - 3] * i) % f[k - 2]) == 0 && (n - f[k - 3] * i) / f[k - 2] >= i) ++ans;
}
printf("%d\n", ans);
}
return 0;
}