学校网站建设机构,好用网站推荐,目前流行的网页设计风格包括,88黄页企业名录链接 理论基础 已知正整数a,v,求证m⌊av⌋是满足⌊am⌋⩾v的最大的m#xff0c;其中x是正整数已知正整数a,v,求证m\lfloor \frac {a}{v} \rfloor是满足\lfloor \frac {a}{m} \rfloor \geqslant v的最大的m#xff0c;其中x是正整数已知正整数a,v,求证m⌊va⌋是满足⌊ma⌋…链接 理论基础 已知正整数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是正整数 先证不等号成立根据整除的定义可以得到先证不等号成立根据整除的定义可以得到先证不等号成立根据整除的定义可以得到 avmr(0⩽rv)avmr(0\leqslant rv)avmr(0⩽rv) ⌊av⌋m\lfloor \frac {a}{v} \rfloorm⌊va⌋m ⌊am⌋⌊vmrm⌋v⌊rm⌋⩾v\lfloor \frac {a}{m} \rfloor\lfloor \frac {vmr}{m} \rfloorv\lfloor \frac {r}{m} \rfloor \geqslant v⌊ma⌋⌊mvmr⌋v⌊mr⌋⩾v 再证这个m是满足不等式的最大的m是m的极限值用反证法再证这个m是满足不等式的最大的m是m的极限值用反证法再证这个m是满足不等式的最大的m是m的极限值用反证法 如果存在这样的数使得不等式成立只需证m1使得这样的不等式成立如果存在这样的数使得不等式成立只需证m1使得这样的不等式成立如果存在这样的数使得不等式成立只需证m1使得这样的不等式成立 ⌊am1⌋⌊vmrm1⌋⌊v(m1)r−vm1⌋v⌊r−vm1⌋\lfloor \frac {a}{m1} \rfloor\lfloor \frac {vmr}{m1} \rfloor\lfloor \frac {v(m1)r-v}{m1} \rfloorv\lfloor \frac {r-v}{m1} \rfloor⌊m1a⌋⌊m1vmr⌋⌊m1v(m1)r−v⌋v⌊m1r−v⌋ 其中r−v是负数根据高斯函数的定义⌊r−vm1⌋⩽−1其中r-v是负数根据高斯函数的定义\lfloor \frac {r-v}{m1} \rfloor \leqslant-1其中r−v是负数根据高斯函数的定义⌊m1r−v⌋⩽−1 ∴⌊am1⌋v\therefore \lfloor \frac {a}{m1} \rfloor v∴⌊m1a⌋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 pairint, 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;
}
