题目链接
本题目的一个推论是：bi中有且仅有一个0
证明：如果最终的数组是 b1, b2 … bn，那么如果存在 2≤i≤n，当 bi>0 且 bi?ai>bi?1 或 b1>0 时，则该解肯定是非最优的。 因为在 bi 或 b1 上有一个不必要的移动。
同样，如果 bi<0 并且 bi+ai 或 bn<0，它也是非最优的。
确定了这一点后，我们只要确定0的位置即可贪心的确认其它值。枚举每个位置为0，取其中答案的最小值。
#include <bits/stdc++.h>
using namespace std;
long long n, a[5005], ans=1e18;
int main()
{
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
}
for (int pos=1; pos<=n; pos++) {
long long prev=0, sum=0;
for (int i=pos-1; i>=1; i--) {
prev+=a[i]-prev%a[i];
sum+=prev/a[i];
}
prev=0;
for (int i=pos+1; i<=n; i++) {
prev+=a[i]-prev%a[i];
sum+=prev/a[i];
}
ans=min(ans, sum);
}
cout << ans << "\n";
return 0;
}
