牛客寒假训练营 2 A(二分，结论，区间合并)

链接 

题目没有说所有攻击牌都必须用完，只是说只要存在一种牌的组合，能够恰好满足伤害值就可以了

限制条件：

某次攻击血量恰好为0开始有一点法力法力没有上限

性质：我们先假设某次 攻击数为a，回复牌数为b

最小伤害和的牌顺序如下，攻击牌和回复牌交替使用

1010101010101010101

最大伤害和的牌顺序如下，回复牌全部用完，然后再用伤害牌

00000000000001111111

在最小伤害和和最大伤害和区间中间的元素都可以通过交换攻击牌和回复牌获得，每次把后面的攻击牌放到回复牌前面去，伤害和-1，把前面的攻击牌放到回复牌后面去，伤害和+1

由于我们知道每次使用伤害牌时必须有蓝，所以伤害牌最多用b+1次，可以得到

a=min(a,b+1)最小伤害和：最大伤害和：

同时，不同攻击牌数他们的最小伤害和，最大伤害和是不同的，比如a-1和a所构成的两个伤害区间是不一定是连续的

为了想要找出最后的答案，需要遍历到一个合适的区间，时间复杂度是O(kn)

想要遍历可以用二分来优化，就可以让时间复杂度变为O(klogn)

#include 
#include 
using namespace std;
int n,m;
typedef long long ll;
ll x;

bool check(int k)
{
	ll minn=1ll*k*k;
	ll maxx=1ll*k*m+1ll*k*(k+1ll)/2ll;
	if(x>=minn&&x<=maxx) return true;
	if(minn>x) return true;
	else return false;
}
int main()
{
	cin>>n>>m;
	n=min(n,m+1);
	int k;
	cin>>k;
	while(k--)
	{
		cin>>x;
		int l=0,r=n;
		while(l>1;
			if(check(mid))
				r=mid;
			else l=mid+1;
		}
		ll maxx=1ll*l*m+1ll*l*(l+1ll)/2ll;
		ll minn=1ll*l*l;
		if(x>=minn&&x<=maxx) 
			cout<<"YESn";
		else cout<<"NOn";
	}
}

通过数学证明，如果a-1和a的区间是连续的，要满足

(a-1)b+a*(a-1)/2  >=a*a-1    a>=b-1

推导得出 a<=4时，不满足区间一定连续，需要特判

依次计算q的各个区间，如下

q.push_back({1,m+1});
q.push_back({4,2*m+3});
q.push_back({9,3*m+6});
q.push_back({16,4*m+10});
q.push_back({25,1ll*n*m+1ll*n*(n+1ll)/2ll});

#include 
#include 
#include 
using namespace std;
int n,m;
typedef long long ll;
pair PII;
vector q;

int main()
{
	cin>>n>>m;
	n=min(n,m+1);
	int k;
	cin>>k;
	q.push_back({1,m+1});
	q.push_back({4,2*m+3});
	q.push_back({9,3*m+6});
	q.push_back({16,4*m+10});
	q.push_back({25,1ll*n*m+1ll*n*(n+1ll)/2ll});
	while(k--)
	{
		ll x;
		cin>>x;
		bool flag=false;
		for(int i=0;i=p.first&&x<=p.second)
				flag=true;
		}
		if(flag) cout<<"YESn";
		else cout<<"NOn";
	}
}