题目描述
卖罐头(数学思维题)
题解(看了好几遍y总的视频写的可以对应视频一起看)
根据题目的已知条件,顾客的计划罐头数x在区间[ L , R ]
之间,问是否存在一个a(题中没有直接给出a的取值范围需要根据题中的条件自己判断)能够满足题中给出的条件x mod a >= a/2
,对于L求出所有满足条件x mod a >= a/2
的最大值a
,取所有a
中的最大值定义为M
,此时M
为所有的a
中满足条件x mod a >= a/2
的最大值,此时判断M
是否大于等于R
,如果M>=R
,则整个区间都有解,反之如果M<R
,则在区间 [ L , R ]
内一定存在一个值不满足条件x mod a >= a/2
,则题目现在的目的变为求满足条件的最大的M
,有根据x mod a >= a/2
,有L>= x mod a >= a/2
,所以a<=2*L
,定义一个L
对a
的余数为y
,则 y = x mod a >= a/2
,则在区间[ L , R ]
内有L+1
的余数为y+1
,L+2
的余数为y+2………
.余数的最大值为a-1
,如果最大值为a
,则余数为0.
现在目的是让[ y , a – 1 ]
区间尽可能长,因为y = x mod a >= a/2
,所以y
的理论最小值为 a/2
.则余数的取值范围变为 [ a / 2 , a – 1 ]
,则区间长度为(a – 1) – (a/2) + 1=a/2
,则区间长度的理论最大值为L
(因为a<=2*L
),因此区间长度的最大值一定小于等于L
,此时需要证明区间长度最大值可以等于L
.
令x=L
, a=2L
,则余数为L
,满足题目条件x mod a >= a/2
,所以可以取到理论最大值
M=2L-1
;
此时只需判断R<=2L-1
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int l,r;
scanf("%d%d",&l,&r);
if(r>=2*l)printf("NO\n");
else printf("YES\n");
}
return 0;
}
第一次写题解