奇怪的顾客(C++)

描述

一家商店的巧克力分为两类包装:

1.散装:一个一个的;

2.盒装:a个巧克力为一盒.

一位顾客购买巧克力时有个奇怪的规矩(假设他需要买x个):

如果x%a>=a/2他就决定全买成盒装,不会再一个一个买了,这会使他买的巧克力比他原来想要的多,此时商家就会高兴。

现在给出这位顾客想要买的巧克力数量的区间 [l,r] (也就是说顾客会选择从l到r的任意数),请你判断是否存在一个整数a使商家在任何情况下都高兴。

输入

第一行输入t 个(t<1000)--案例个数

接下来tt行每行输入两个数:x的范围l和r (0<l<=r<5000),两数中间以一个空格隔开

输出

输出为t行。对于每个案例,如果存在整数a使得商家在顾客的所有选择下都会高兴,则输出"YES",否则输出"NO"(输出不包含"")。

输入样例 1 

3
3 4
1 2
120 150

输出样例 1

YES
NO
YES

思路:

其实是一个数学问题。可以推算一下。首先a一定是从2开始算起(a==1的话无意义)。

如果a<l,(单独考虑2,3的情况发现没有合适的a)考虑到l与r之间肯定有合数,那么在遍历的过程中,只要a==2(或其他合适的因数),x%a将在某一个x值处取到0,不符合题意,舍去;

如果a>l&&a>r,那么x%a==l或==r,这就是一个确定的数了,接下来只要考虑让这两个数值>=a/2,即联立四个方程组求解取交集

a>l

a>r

l>=a/2

r>=a/2

解得r<a<=2l

所以当右边界小于等于左边界的时候都是不存在的,输出NO就可以了。

(为什么不考虑中间:我先考虑的边界,然后发现考虑到最大的边界的时候就过了)

代码如下:

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		if (2 * l <= r)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
	return 0;
}

上一篇:centos7 配置ftp服务器搭建(匿名访问,以及本地登录)


下一篇:centos 安装vsftp