2025杭电多校第七场 矩形框选、伤害冷却比 个人题解

伤害冷却比

数学

题目

思路

令\(a=\frac{K}{N}\)，则有\(f(x)=x\left( \left\lfloor  \frac{a}{x}  \right\rfloor +1\right)\)
大致画出图像，可得下图

若要求区间\([L,R]\)上的最大值，则需要求出\(f(R)\)与红线蓝线交点值之间的最大值
为了求出交点，联立两个方程：

\[\begin{align}x+a&=x\left( \left\lfloor  \frac{a}{x}  \right\rfloor +1 \right)\\ \\x+a&=x\left\lfloor  \frac{a}{x}  \right\rfloor +x\\ \\\frac{a}{x}&=\left\lfloor  \frac{a}{x}  \right\rfloor \\ \\\exists \ n\in& Z\ , \frac{a}{x}=n\\ \\\therefore x=\frac{a}{n}&,n=1,2,3,\dots\end{align}\]
因此可以找到距离\(R\)最近的\(x_{0}=\frac{a}{n}\)，其中\(n=\left\lceil  \frac{a}{R}  \right\rceil\)
再将此\(x_{0}\)带入\(y=x+a\)中，即可得到区间\([L,R]\)上交点的最大值啦
随后将\(R\)带入\(f(x)\)中，比较二者大小约分输出即可
代码实现

[code]#include#include#include#include#include#include#include#include#includeusing namespace std;using ll = long long;#define rep(i, a, b) for(ll i = (a); i = (b); i --)#define see(stl) for(auto&ele:stl)coutN>>A>>B>>C>>D;    int n=ceil(1.0*(K*D)/(N*C));    double x=1.0*K/(N*n);    double ans1=x+(1.0*K/N);    double L=1.0*A/B;    if(L>x)ans1=-1;    double ans2=1.0*C/D*(K*D/(N*C)+1);    if(ans1>=ans2){        int g=gcd(K*(1+n),N*n);        cout