CF1646B 题解

题目传送门

\(\color{red}{see}\space \color{green}{in}\space \color{blue}{my}\space \color{purple}{blog}\)

看到题解里没有用双指针往中间靠的写法的，果断来一发。

思路上是贪心，贪心原则如下。

• 任何时候保证蓝色元素比红色元素数量多。

• 每次给剩余的最小元素涂蓝色，给最大元素涂红色。

• 如果此时红元素的和大于蓝元素的和，说明可以成立。

• 如果所有元素都被涂上色了，但还没有成立，说明无法构造。

有了这个思路就很容易了，我们先给数据排序。

sort(a+1, a+n+1);

然后创建双指针，注意和需要使用 long long。

int L = 1; long long sumL = a[1];    //左指针初始化，对应蓝色。 
int R = n+1; long long sumR = 0;     //右指针初始化，对应红色。

接下来两个指针不断朝中靠拢即可。

while (L < R) //注意此处是小于不是小于等于。
{
	if (sumR > sumL) return true;
	sumL += a[++L];   //等价于 L++, sumL += a[L];
	sumR += a[--R];   //等价于 R++, sumR += a[R];
}
return false; 

把几段代码整理一下即可。

完整代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
int a[200005];
bool solve()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(a+1, a+n+1);
	int L = 1; LL sumL = a[1];  //左指针初始化，对应蓝色。 
	int R = n+1; LL sumR = 0;     //右指针初始化，对应红色。
	while (L < R) //注意此处是小于不是小于等于。
	{
		if (sumR > sumL) return true;
		sumL += a[++L];
		sumR += a[--R];
	}
	return false; 
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		if (solve()) puts("YES");
		else puts("NO");
	}
	return 0;
}

首发：2022-04-13 09:56:57