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;
}