Antiamuny 还在学习二分!所以他又通过不同的语言实现了一个二分的子程序:
Antiamuny 还在学习二分!所以他又通过不同的语言实现了一个二分的子程序: C/C++: int f(int l,int r,int x) { // l <= x <= r int cnt = 0; while(l <= r) { cnt++; int mid = (l + r) / 2; if (mid == x) break; if (mid < x) l = mid + 1; else r = mid - 1; } return cnt; } Java: public static int f(int l,int r,int x) { // l <= x <= r int cnt = 0; while(l <= r) { cnt++; int mid = (l + r) / 2; if (mid == x) break; if (mid < x) l = mid + 1; else r = mid - 1; } return cnt; } Python: def f(l, r, x): # l <= x <= r cnt = 0 while l <= r: cnt += 1 mid = (l + r) // 2 if mid == x: break elif mid < x: l = mid + 1 else: r = mid - 1 return cnt 可以发现,上述程序实现了在 [L,R][L,R][L,R] 中寻找 xxx 并且返回了 while 循环的运行次数 cntcntcnt。 在第 21 届上海大学程序设计联赛春季赛中,Antiamuny 非常好奇:对于给定的 LLL, RRR, xxx,函数 f(L,R,x)f(L,R,x)f(L,R,x)返回的 cntcntcnt 是多少。 所有人都帮助 Antiamuny 解决了这个问题!但是现在 Antimauny 有了新的疑惑: 对于给定的LLL, RRR, cntcntcnt,在范围 [L,R][L,R][L,R] 中是否存在一个 xxx 使得 f(L,R,x)=cntf(L,R,x)=cntf(L,R,x)=cnt。
标签: HBC258603华丽转身 贪心 动态规划Antiamuny wants to leaern binary search again题解