题目如下：

TokitsukazeTokitsukazeTokitsukaze 有一个函数
f(x)=⌊xn⌋+x−1f(x)=⌊\frac{x}{n}⌋+x−1f(x)=⌊nx⌋+x−1
她想在区间 [L,R][L,R][L,R] 中找到一个最小的整数 ttt, 使函数 f(t)f(t)f(t) 的值最小。

输入描述:

第一行包含一个整数 TTT (1≤T≤2∗105)(1 \le T \le 2*10^5)(1≤T≤2∗105), 表示测试数据组数。
每组测试数据包含三个整数 n,L,Rn,L,Rn,L,R (1≤n≤1018(1 \le n \le 10^{18}(1≤n≤1018; 1≤L≤R≤1018)1 \le L \le R \le 10^{18})1≤L≤R≤1018)。

输出描述:

对于每组测试数据，输出最小的 ttt (L≤t≤R)(L \le t \le R)(L≤t≤R), 使 f(t)f(t)f(t) 的值最小。

示例1

输入

链接：https://ac.nowcoder.com/acm/contest/46810/E
来源：牛客网11
9 1 1
9 1 2
9 1 3
9 1 4
9 1 5
9 5 6
9 5 7
9 5 8
9 5 9
1145141919810 114514 1919810
8 1 8

输出

说明

n=9n = 9n=9 时，f(1)=9,f(2)=5,f(3)=5,f(4)=5,f(5)=5,f(6)=6,f(7)=7,f(8)=8,f(9)=9f(1) = 9, f(2) = 5, f(3) = 5, f(4) = 5, f(5) = 5, f(6) = 6, f(7) = 7, f(8) = 8, f(9) = 9f(1)=9,f(2)=5,f(3)=5,f(4)=5,f(5)=5,f(6)=6,f(7)=7,f(8)=8,f(9)=9

题解 or 思路：

首先我们可以发现这个函数是 凹函数

赛时写了个三分 wawawa 了, 为什么呢？
应为这个题中的 xxx 正整数，我们只能保证在实数上这个函数是凹函数有且只有应该峰，但如果取值是正整数，我们无法保证其的单调性。

我们可以知道这个函数在 sqrt(n)sqrt(n)sqrt(n) 处取得最小值，但我们不确定是在 n\sqrt{n}n 还是在 ⌊n⌋⌊\sqrt{n}⌋⌊n⌋ 处。

我们可以分类去求解：

L>nL > \sqrt{n}L>n 答案就是 LLL
其他情况
令 f(t0)f(t_0)f(t0) 为最小的 f(x)f(x)f(x)，现在要求最小的 ttt。显然在 [1,t0][1,t_0][1,t0] 内的 fff 是单调递减的，所以我们可以在 [L,t0][L,t_0][L,t0] 范围内二分求出 ttt。时间复杂度 O(T⋅logn)O(T · log n)O(T⋅logn)

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define buff                     \ios::sync_with_stdio(false); \cin.tie(0);
// #define int long long
#define ll long long
#define PII pair
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 100009;
// int Mod(int a,int mod){return (a%mod+mod)%mod;}
// int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
// int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
// int inv(int a,int mod){return qmi(a,mod-2,mod);}
// int lcm(int a,int b){return a*b/__gcd(a,b);}
ll n, l, r;
void solve()
{cin >> n >> l >> r;auto cal = [](ll x){return n / x + x - 1;};ll x = sqrt(n);if (l > x){cout << l << '\n';return;}if (r > x)r = x + (cal(x) >= cal(x + 1));ll mn = cal(r);ll ans = r;while (l < r){ll mid = l + r >> 1;if (cal(mid) <= mn)ans = mid, r = mid;elsel = mid + 1;}cout << ans << '\n';
}
int main()
{buff;int _;cin >> _;while (_--)solve();
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：企业级Jenkins实践

下一篇：数据治理：数据治理之道-数据文化-数据思维融入企业文化

2023牛客寒假算法基础集训营2 -- E-Tokitsukaze and Function(数学二分)

题目如下：

输入描述:

输出描述:

示例1

输入

输出

说明

题解 or 思路：

AC 代码如下：

相关内容

热门资讯

2023牛客寒假算法基础集训营2 -- E-Tokitsukaze and Function(数学 二分)

题目如下：

输入描述:

输出描述:

示例1

输入

输出

说明

题解 or 思路：

AC 代码如下：

相关内容

热门资讯

2023牛客寒假算法基础集训营2 -- E-Tokitsukaze and Function(数学二分)