CF1705A Mark the Photographer 题解

题意：

给定一队人的身高，将其分成两队，问能否实现前面的人均低于后面的人至少 \(x\) 个单位长度。

做法：

将这队人的身高进行排序，\(h_1 \sim h_n\) 即为第一队，\(h_{n+1} \sim h_{2n}\) 即为第二队，两队前后进行比较即可。

证明：

将其身高进行排序之后，若第 \(i\) 与第 \(n+i\) 个无法满足条件，那么第 \(n+i\) 与其它的也无法满足条件，因为排序后具有单调性。

注意：

排序的时候应为 \(1\)~\(1+n+n\) 个区域上的数值。

#include <cstdio>

#include <iostream>

#include <algorithm>//sort头文件

using namespace std;

int t;

int n,x;

int h[1000005];//储存身高

int main()

{

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d%d",&n,&x);

		for(register int i=1;i<=n*2;i++)

		{

			scanf("%d",&h[i]);

		}

		sort(h+1,h+1+n+n);//排序

		bool flag=false;

		for(register int i=1;i<=n;i++)

		{

			if(h[i+n]-h[i]<x)//如果前面的高于后面的或后面的高于前面的并没有x

			{

				puts("NO");//输出

				flag=true;//标记

				break;

			}

		}

		if(!flag) puts("YES");//如果并没有标记，输出YES

	}

	return 0;

}

巴特西

CF1705A Mark the Photographer 题解

题意：

做法：

证明：

注意：

最新文章

热门文章