「bsoj1692」变 - 模拟

题目大意

$zhx$手上有$N$个数$a_i$，和另外两个数$A$和$B$，满足$A\lt B$。现在，你需要做一个游戏。游戏中的每一轮中，你可以做如下两种操作之一：

1. 执行$A=A-1$。
2. 选择一个$1$到$N$之间的数$x$，执行：$A=A-(A\bmod a_x)$

zhx 和他的妹子玩游戏去了，现在zhx 希望聪明的你告诉他，至少通过多少轮操作，可以使得$A=B$。

---

题目分析

可以证明，每一次使得$A$变得更小是更优的。
然后就可以暴力了，每一次在$a[]$中选出一个可以使$A$变得最小的数，如果$a_i$使得$A\lt B$，就将$a_i$删掉。

不知道为什么暴力可以过，标解好像也是暴力。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
set<int>a;
int n,ans=0;
int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a.insert(Get_Int());
	int A=Get_Int(),B=Get_Int();
	while(A>B) {
		int Min=A-1;
		vector<int>del;
		for(auto i=a.begin(); i!=a.end(); i++) {
			int x=*i;
			if(A-A%x<B)del.push_back(x);
			else Min=min(Min,A-A%x);
		}
		for(auto& x:del)a.erase(x);
		A=Min;
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}