AcWing 3725. 卖罐头
原题链接
简单
作者:
代码改变头发
,
2021-06-24 19:55:32
,
所有人可见
,
阅读 336
算法思路
问是否存在a,使得任意x[L,R], x % a >= a / 2.
思路:固定L, 对于任意a均存在一个区间[L,U]满足上述条件, 设R‘ = max(U), 判断R'>=R是否成立.
若成立则存在a(a取使得U=R'的值即可),否则不存在.
L >= L mod a >= a/2 ==> a <= 2L
对于每个a,区间可以表示为[k*a + b, k * a + c ], 而 a/2 <= b , c < a
所以区间长度最大值为 a - 1 - a / 2 + 1 = a / 2.
a <= 2L , 那么 a 能取到2L吗?
设 a = 2L, L % 2L >= a / 2满足条件,所以区间长度的最大值可以取到L ==> R' = L + L - 1 = 2L - 1
所以我们只需要判断 2L-1 >= R 是否成立即可.
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
while( T-- )
{
int l, r;
cin >> l >> r;
if( 2 * l - 1 >= r ) puts("YES");
else puts("NO");
}
return 0;
}