AcWing 1205. 买不到的数目(丑数式枚举)
原题链接
简单
作者:
1733478157
,
2021-03-06 18:28:20
,
所有人可见
,
阅读 1265
#include<iostream>
#include<vector>
using namespace std;
int x,y;
vector<int> v;
int main()
{
cin >> x >> y;
int end = min(x,y);//只要有连续end个数可以买到后面的就一定可以买到
int i = 0,j = 0;
v.push_back(0);
int ans = 0;
int cnt = 1;
while(true){
int t = min(v[i]+x,v[j]+y); // 类似与丑数的枚举
if(v.back() != t) { // 这个有可能有相同的数,就跳过
if(t == v.back()+1) cnt++;
else cnt = 1,ans = t-1;//每一次中断就更新答案
v.push_back(t);
}
if(t == v[i]+x) i++;
if(t == v[j]+y) j++;
if(cnt == end) break;
}
cout << ans << endl;
return 0;
}
# 巨佬巨佬