C-第K小表示数_牛客小白月赛78 (nowcoder.com)
问题：
分析:
k的极限是1e6,因此要几乎O(n)的时间复杂度给求出来，还需要每插入一个元素我都要去排序，这个时候set就派上用场了，自带排序和去重,集合里面最小和第二小的一定是min(a, b)和max(a, b)因为集合里面其他的数都是通过a或者是b去构造(+)的，因此他们都比a，b大，要想每次加的数小，我就去枚举集合里面的每个数 然后把这个数与a和b分别相加，把相加的结果 插入到集合set里面
代码：
#include<bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;int k, a, b;
string s;
set<int>se; signed main() {cin >> k >> a >> b;se.insert(a);se.insert(b);int x;while(k--) {x = *se.begin();se.erase(x);//这个一定要去删除掉 删除的话 还可以为结果做铺垫 /*假如不删除的话 每次取到的x一定只能是min(a, b)了 那么插入(a + x)和 (b + x)的值就是定的了 假如不删除的例子:刚开始集合{1, 2}第一次 {1, 2, 3}第二次 {1, 2, 3}第三次 {1, 2, 3}...... */ se.insert(a + x); se.insert(b + x);} cout << x << endl;return 0;
}
