阿里云网站建设长沙网站seo优化公司

链接
理论基础
$已知正整数a,v,求证m=\lfloor \frac{a}{v}\rfloor 是满足\lfloor \frac{a}{m}\rfloor ⩾v的最大的m，其中x是正整数$
$先证不等号成立根据整除的定义可以得到$
$a=vm+r(0⩽r<v)$
$\lfloor \frac{a}{v}\rfloor =m$
$\lfloor \frac{a}{m}\rfloor =\lfloor \frac{vm+r}{m}\rfloor =v+\lfloor \frac{r}{m}\rfloor ⩾v$
$再证这个m是满足不等式的最大的m，是m的极限值，用反证法$
$如果存在这样的数使得不等式成立，只需证m+1使得这样的不等式成立$
$\lfloor \frac{a}{m+1}\rfloor =\lfloor \frac{vm+r}{m+1}\rfloor =\lfloor \frac{v(m+1)+r-v}{m+1}\rfloor =v+\lfloor \frac{r-v}{m+1}\rfloor$
$其中r-v是负数，根据高斯函数的定义，\lfloor \frac{r-v}{m+1}\rfloor ⩽-1$
$\therefore \lfloor \frac{a}{m+1}\rfloor <v$
$故不存在更大的m了$
分析
这道题，由于数值比较小，我们考虑枚举下限0~a[0],虽然有些数值不一定取到但是没有关系，因为，如果真的没有任何一个数能够取到的话，只要改变数值的大小就可以使得某一个数取到，这样差值就会变小，刚刚的非法的答案就不会有影响。对于某个下限，我们枚举最大的p使得不等式成立，也就是让整除结果尽可能接近v使得差值最小。因为差值最小是零，所有我们可以枚举所有的下限，尽管可能有些数是取不到的但是这些下限必然是不少最终的 答案，所有没有关系。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 3005;
int a[N];
void solve() {int n, k;cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];int ans = inf;for (int i = 0; i <= a[1]; i++) {int maxn = 0;for (int j = 1; j <= n; j++) {int x = min(k, (i ? (a[j] / i) : k));//居然不考虑零也是可以的，我也是很迷惑的，如果真的想不到这个东西其实也是可以用二分的maxn = max(maxn, a[j] / x);}ans = min(ans, maxn - i);}cout << ans << '\n';
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}