爱吃咸鱼的喵の无名小站 > UVa1618 弱键

UVa1618 弱键

2019-01-18

暴力枚举, 二分法

UVa1618解题报告

题目链接
这题目又是用到二分法，感觉自己对二分用的还是不很灵活，总结一下思路，希望自己能有点突破吧~

思路分析

  根据题目意思，给定一个数组判断其中是否含有四个满足如下条件的元素：

$N_p,N_q,N_r,N_s$ 满足条件$1<=p=N_s>=N_p>=N_r或者N_q<=N_s<=Np<=Nr$


  最简单想到的是暴力枚举四个数，判断所有情况,时间复杂度为$O(n^4)$，根据题目给出的数量级，这样肯定超时，我们至少要设计出$O(n^2\log{n})$的算法。
  这种题常用的做法是减少枚举的变量的个数，通过枚举一部分变量，设计算法快速找到剩下满足条件的变量
  想到这里就不难了，这道题思路和刘汝佳书上的UVa1152和为0的4个值思路差不多，如果能只枚举两个数，而通过$O(1)$或者$O(\log{n})$的算法找出剩下满足条件的两个数是否存在，那么总体的算法复杂度即为$O(n^2\log{n})$或者$O(n^2)$

算法设计

  题目中的两个条件，我们只用考虑一种情况，另外一种可以通过倒转数组来判断得到结果。四个数之中$q、r$位于中间位置，而恰好又是最大值和最小值，我们可以枚举中间这两个数字$N_q,N_r$，然后在左端快速找到$N_p$,在右端快速找到$N_s$。
  这里用到了贪心的思想，我们在下标小于$q$的元素中找到不超过$N_r$的最大元素（为了给$N_s$留出尽量多的候选位置）即为$N_p$，而在下标大于$r$中找到不小于$N_q$的最小元素即为$N_s$。
  通过上面分析可知，我们需要在$O(1)$或者$O(\log{n})$时间内找到这两个元素，不难想到可以通过预处理得出每个元素左边比所有它大的元素、以及在它右边所有比它小的元素，排序之后，通过二分查找就可以在$O(\log{n})$时间内找到需要的元素。（不过我想了想，好像不用预处理，直接对左右的数排序然后二分查找也行-_-||）。最后再判断是否满足$N_p>N_s$
  具体思路如下：

  • 首先扫描一遍数组，用两个vector分别保存当前位置左边比它大的数，以及当前位置右边比它小的数，之后对两个vector排序
  • 枚举中间两个数字，首先判断枚举的两个数字$N_q、N_r$是否符合条件，之后再用二分法找到最优的$N_p、N_s$判断是否满足条件
  • 如果找到解，那么返回true，否则枚举完所有位置都没解，那么返回false。
  • 最后将原数组翻转一次，在进行判断

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
const int maxn = 5000 + 1000;
int k;
int ACM[maxn];

vector<int> L[maxn], R[maxn];

bool judge()
{
	//预处理,找出对于每一个数，左边比他大，而右边比他小的数
	for (int i = 0; i < k; i++)
	{
		L[i].clear();
		R[i].clear();

		for (int j = i - 1; j >= 0; j--) if (ACM[j] > ACM[i]) L[i].push_back(ACM[j]);
		for (int j = i + 1; j < k; j++) if (ACM[j] < ACM[i]) R[i].push_back(ACM[j]);

		//排序为之后的二分做准备

		sort(L[i].begin(), L[i].end());
		sort(R[i].begin(), R[i].end());
	}

	//下面进行二分查找，首先枚举中间两个数，分别是最大值和最小值

	for(int i=0;i<k;i++)
		for (int j = i + 1; j < k - 1; j++)
		{
			//如果满足条件
			if (ACM[i] < ACM[j]&&L[i].size()>0&&R[j].size()>0)
			{
				//贪心解法
				//进行二分查找,往左侧找出小于 ACM[j] 最大的数字
				int p = lower_bound(L[i].begin(), L[i].end(), ACM[j]) - L[i].begin();
				//在右侧找出大于ACM[i]最小的数字
				int s = upper_bound(R[j].begin(), R[j].end(), ACM[i]) - R[j].begin();

				//如果找不到会越界，需要判断
				if (p == 0 || s == R[j].size()) continue;

				//判断是否满足题目条件
				if (L[i][p-1] > R[j][s])  return true;
			}

			
		}

	return false;
}


bool solve()
{
	bool ok1 = judge();
	reverse(ACM, ACM + k);
	bool ok2 = judge();
	return ok1 || ok2;
}

int main()
{
	int T;
	freopen("C:\\Users\\lenovo\\Desktop\\test\\in.txt", "r", stdin);
	freopen("C:\\Users\\lenovo\\Desktop\\test\\out.txt", "w", stdout);
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &k);
		for (int i = 0; i < k; i++)
			scanf("%d", &ACM[i]);
		bool ok = solve();
		if (ok)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

每天进步一点点~

参考资料
http://www.cnblogs.com/sugewud/p/9819562.html