C. Tiles Comeback

原创于 2023-08-08 22:49:43 发布 · 粉丝可见 · 156 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132177928

题目：

样例：

10 4 2 1 1 1 1 14 3 1 2 1 1 7 5 3 3 1 3 4 4 2 4 3 3 3 1 3 10 4 1 2 1 2 1 2 1 2 1 2 6 2 1 3 4 1 6 6 2 2 1 1 4 2 2 1 1 1 2 1 1 2 3 2 2 2 2 4 1 1 1 2 2

YES YES NO NO YES YES NO YES YES YES

解释：

思路：

单纯思维题，还是得要多练练，查看规律，

题目意思，是 k 是至少铺路的长度，这里是找出前面第一个元素所铺的路和最后一个元素所铺的路之和要满足 k 的倍数，可以换个思维，让它们 >= k 也会称为 k 的倍数，因为也有可能加上中间的一些没有涂颜色的路,而这里有两种情况

第一种：前后元素相同的，所以我们只要这个元素的总和 >= k

第二种：不同的时候，我们要先找到前面元素数量满足>=k ，再找最后元素数量是否 >= k

代码如下：

#include <iostream>
#include <unordered_map>
#define umap unordered_map
using namespace std;
const int N = 2e6 + 10;
 
inline void solve()
{
	int n, k;
	umap<int, int>r, arr;
	cin >> n >> k;
	for (int i = 0, num; i < n; ++i)
	{
		cin >> arr[i];
		r[arr[i]]++;
	}
	if (arr[0] == arr[n - 1] && r[arr[0]] >= k)
	{
		puts("YES");
		return ;
	}
	if (arr[0] != arr[n - 1])
	{
		for (int i = 0, l = 0, r = 0; i < n; ++i)
		{
			if (arr[i] == arr[0])
				++l;
			if (l >= k && arr[i] == arr[n - 1])
			{
				++r;
				if (r >= k)
				{
					puts("YES");
					return ;
				}
			}
		}
	}
	puts("NO");
	return ;
}
 
int main()
{
	int _t;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}