atcoder Moderate Differences(数学)

xiaoxiao2021-02-27  143

题意:

给你一序列最左边b和最右边的数a,这个序列要求相邻的数的差距的绝对值得在c和d之间,序列的个数为n,问能不能构造出这样的合法序列。

思路:

这个题是真的巧。

总共有n个数,就有n-1个相邻的数的差,记每个差为f[i],那么所有的f[i]的和就是b-a,这个容易想。

f[i]的取值范围为【-d,-c】U【c,d】之间。

假设有m个数是在【-d,-c】之间,那么如果f[i]的和的取值范围就是【(n-1-m)*c-d*m,(n-1-m)*d-c*m】,假如b-a也在这个范围的话, 就说明我们一定能构造出这样一个序列,

需要从0到n-1去枚举m然后o(1)判断就可以了。

代码:

#include <bits/stdc++.h> using namespace std; int main() { long long a, b, c, d, n; cin>>n>>a>>b>>c>>d; n--; for(int i=0; i<=n; i++) { if((c*(n-i)-d*i)<=(b-a) && (b-a)<=(d*(n-i)-c*i)) { return 0*printf("YES\n"); } } printf("NO\n"); }

转载请注明原文地址: https://www.6miu.com/read-16571.html

最新回复(0)