题意：给你一个数组xi和两个数a和b，求通过两个途径由a到b的最小次数，1.当前的a减去1，2.当前的a减去a%xi。
思路：首先考虑xi有重复元素，所以去重，然后当a-a%x[i]小于b时那么无论怎么变化a-a%x[i]也必定小于b，所以x的个数是逐渐变少的，那么知道这两个之后用贪心的方法找是1途径还是2，最后直到a==b。
代码如下：
#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
int x[100005];
int main()
{
int n;LL a,b;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lld",&x[i]);
}
int sum=0;
scanf("%lld%lld",&a,&b);
if(a==b)
{
printf("0\n");return 0;
}
sort(x,x+n);
int len=unique(x,x+n)-x;
while(a>b)
{
if(a-1==b)
{
sum++;break;
}
LL ans=-1;
for(int i=0;i<len;i++)
{
if(a-(a%x[i])>=b)
{
if(ans<(a%x[i]))
{
ans=a%x[i];
}
}
else
{
x[i--]=x[--len];
}
}
if((a-1)<=(a-ans))
{
sum++;a-=1;
}
else
{
sum++;a-=ans;
}
//printf("#%lld %lld ",a,ans);
if(a==b) break;
}
printf("%d\n",sum);
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
