#include <iostream> int query(int n, int *a, int x) { int l = 0, r = n; while (l < r) { int mid = l + (r - l) / 2; if (a[mid] >= x) r = mid; else l = mid + 1; } if (l == n) return -1; return l; } int main() { int n = 10; int x = 3; int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7}; std::cout << query(n, num, x) << "\n"; return 0; }
#include <iostream> using namespace std; int f(int n) { if (n <= 2) return n * 2; return f(n - 1) + f(n - 2); } int main() { cout << f(5) << endl; return 0; }
A国有 $n$ 座城市，城市之间由 $m$ 条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以 $1, 2, \dots, n$ 编号。第 $i$ （$1 \le i \le m$）条双向道路连接城市 $u_i$ 与城市 $v_i$。
对于城市 $u$ 和城市 $v$ 而言，它们之间的连通度 $d(u, v)$ 定义为从城市 $u$ 出发到达城市 $v$ 所需经过的双向道路的最少条数。由于道路是双向的，可以知道连通度满足 $d(u, v) = d(v, u)$，特殊地有 $d(u, u) = 0$。
现在 A国正在规划城市建设方案。城市 $u$ 的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市，如果有多个满足条件的城市，则选取其中编号最小的城市。形式化地，你需要求出使得 $\max_{1 \le i \le n} d(u, i)$ 最小的 $u$，若存在多个可能的 $u$ 则选取其中最小的。
第一行，两个正整数 $n, m$，表示 A国的城市数量与双向道路数量。
接下来 $m$ 行，每行两个整数 $u_i, v_i$，表示一条连接城市 $u_i$ 与城市 $v_i$ 的双向道路。
输出一行，一个整数，表示建设难度最小的城市编号。如果有多个满足条件的城市，则选取其中编号最小的城市。
3 3 1 2 1 3 2 3
1
4 4 1 2 2 3 3 4 2 4
2
对于 $40\%$ 的测试点，保证 $1 \le n \le 300$。
对于所有测试点，保证 $1 \le n \le 2000$， $1 \le m \le 2000$, $1 \le u_i,v_i \le n$。
班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以 $1, 2, \dots, n$ 编号，第 $i$ 名同学有其发言积极度 $c_i$。
观察发现，如果一个学习小组中恰好包含编号为 $p_1, p_2, \dots, p_k$ 的 $k$ 名同学，则该学习小组的基础讨论积极度为 $a_k$，综合讨论积极度为 $a_k + \max\{c_{p_1},c_{p_2}, \dots, c_{p_k} \} - \min\{c_{p_1},c_{p_2}, \dots, c_{p_k}\}$，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。
给定基础讨论积极度 $a_1, a_2, \dots, a_n$，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。
第一行，一个正整数 $n$，表示班级人数。
第二行，$n$ 个非负整数 $c_1, c_2, \dots, c_n$，表示每位同学的发言积极度。
第三行，$n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示不同人数学习小组的基础讨论积极度。
输出一行，一个整数，表示所有划分方案中，学习小组综合讨论积极度之和的最大值。
4 2 1 3 2 1 5 6 3
12
8 1 3 2 4 3 5 4 6 0 2 5 6 4 3 3 4
21
对于 $40\%$ 的测试点，保证 $c_i = 0$。
对于所有测试点，保证 $1 \le n \le 300$， $0 \le c_i \le 10^4$， $0 \le a_i \le 10^4$。
