深圳 德 网站建设搜索引擎调词平台价格
链接
理论基础
已知正整数a,v,求证m=⌊av⌋是满足⌊am⌋⩾v的最大的m，其中x是正整数已知正整数a,v,求证m=\lfloor \frac {a}{v} \rfloor是满足\lfloor \frac {a}{m} \rfloor \geqslant v的最大的m，其中x是正整数已知正整数a,v,求证m=⌊va⌋是满足⌊ma⌋⩾v的最大的m，其中x是正整数
先证不等号成立根据整除的定义可以得到先证不等号成立根据整除的定义可以得到先证不等号成立根据整除的定义可以得到
a=vm+r(0⩽r<v)a=vm+r(0\leqslant r<v)a=vm+r(0⩽r<v)
⌊av⌋=m\lfloor \frac {a}{v} \rfloor=m⌊va⌋=m
⌊am⌋=⌊vm+rm⌋=v+⌊rm⌋⩾v\lfloor \frac {a}{m} \rfloor=\lfloor \frac {vm+r}{m} \rfloor=v+\lfloor \frac {r}{m} \rfloor \geqslant v⌊ma⌋=⌊mvm+r⌋=v+⌊mr⌋⩾v
再证这个m是满足不等式的最大的m，是m的极限值，用反证法再证这个m是满足不等式的最大的m，是m的极限值，用反证法再证这个m是满足不等式的最大的m，是m的极限值，用反证法
如果存在这样的数使得不等式成立，只需证m+1使得这样的不等式成立如果存在这样的数使得不等式成立，只需证m+1使得这样的不等式成立如果存在这样的数使得不等式成立，只需证m+1使得这样的不等式成立
⌊am+1⌋=⌊vm+rm+1⌋=⌊v(m+1)+r−vm+1⌋=v+⌊r−vm+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⌊m+1a⌋=⌊m+1vm+r⌋=⌊m+1v(m+1)+r−v⌋=v+⌊m+1r−v⌋
其中r−v是负数，根据高斯函数的定义，⌊r−vm+1⌋⩽−1其中r-v是负数，根据高斯函数的定义，\lfloor \frac {r-v}{m+1} \rfloor \leqslant-1其中r−v是负数，根据高斯函数的定义，⌊m+1r−v⌋⩽−1
∴⌊am+1⌋<v\therefore \lfloor \frac {a}{m+1} \rfloor <v∴⌊m+1a⌋<v
故不存在更大的m了故不存在更大的m了故不存在更大的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;
}