题目描述
由n个罐头,分成k组a个的包和n-k*a个单独的(k为满足条件最大整数),要求判断是否存在a使得当n~[l,r]时,剩余的n-k*a都满足大于等于a/2.
输入样例
n,
剩余n行每行l,r
3
3 4
1 2
120 150
输出样例
YES
NO
YES
算法1
(暴力枚举) $O(n^2)$
可以看到我的代码很短(简单题),因为如果l与r的距离大于等于l,则必定存在n~[l,r],使得l*k=n,即n-k*a=0,即不满足题意.
举个例子
l=3,r=8,存在n=6=2*l,因为l与r的间距缘故,所以上面推理成立
当l与r的距离小于l,即r$<$2*l,当a取r+1,l$>$=a/2(向下取整),r$<$a,所以所有n~[l,r]都满足a/2<=n$<$a,即满足题意
举个例子
l=4,r=7,存在a=8,使得任意n~[4,7]都满足n-k*a$>$=a/2
时间复杂度
emmmmmmmmmmmm.......
参考文献
C++ 代码
#include<iostream>
using namespace std;
int l,r,t;
int a[10010];
int main(){
cin>>t;
while(t--){
cin>>l>>r;
if(l*2>r)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla