洛谷题解——P1114：“非常男女”计划

大家好，欢迎来到IT知识分享网。

题目相关

题目链接

洛谷，https://www.luogu.com.cn/problem/P1114。

计蒜客，https://nanti.jisuanke.com/t/T1853。

我的OJ，http://47.110.135.197/problem.php?id=5252。

题目描述

近来，初一年的XXX小朋友致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。

万圣节来临之际，XXX准备在学校策划一次大型的“非常男女”配对活动。对于这次活动的参与者，XXX有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，XXX当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

输入格式

第一行有一个正整数 n，代表学校的人数。n ≤

第二行有 n 个用空格隔开的数，这些数只能是 0 或 1，其中，0 代表一个女生，1 代表一个男生。

输出格式

输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子序列长度。

如果不存在男女人数相等的子序列，请输出 0。

输入样例

9 0 1 0 0 0 1 1 0 0

输出样例

题目分析

题意分析

找出 n 个长度数列中，最长的子序列 [l, r]，该子序列包含相同多的 0 和 1。这个什么意思？我们思考一下。数组中的数组只有 0 和 1 两种。假设 [l, r] 之前有 x 个元素，那么 $\sum_{i=l}^{r}a_i$ 的值应该是多少呢？聪明的你是不是立马想到了，这个和应该是 $\frac{x}{2}$ 。现在应该可以反应出，首先我们需要计算前缀和。

样例数据分析

输入样例数据为 [0 1 0 0 0 1 1 0 0]，那么对应的前缀和为 [0 0 1 1 1 1 2 3 3 3]。由于题目要求我们是想同的男生女生，意味着结果必然为偶数。样例数据为 9 个，因此最大的长度只能为 8。思路就是能否找到 2、4、6、8 个的子序列。下面我们绘制一个表格，来模拟一下暴力计算的过程。

l	r	人数	sum[r]-sum[l-1]	符合？	备注
2	9	8	3-0=3	✘
1	8	8	3-0=3	✘
4	9	6	3-1=2	✘
3	8	6	3-1=2	✘
2	7	6	3-0=3	✔	6人可以，就不需要验证 4 人组合

如上表所示，最终最长的序列为 6。

数据范围分析

根据题目提供的数据范围，我们可以知道 n 最大值为 10000，因此 $O(n^{2})$ 复杂度的算法是没有办法通过的。由于数据量比较小，我们可以进行减枝操作，参考上面的思路，勉强可以通过。根据最不利原则，我们可以知道，算法的复杂度变为 $O(\frac{1}{2}n^{2})$ （实际是没有这个复杂度的）。

算法优化

能否将上面的 O(nlogn) 算法优化为 O(n)？

我们需要对原始数据进行简单处理。原数据中，女生用 0 表示，男生用 1 表示，我们将其改为对称，即女生用 -1 表示，男生用 1 表示，这样只要是成对的男生女生，对应和为 0。下面我们同样用样例数据进行分析：

序号	1	2	3	4	5	6	7	8	9
原始数据	0	1	0	0	0	1	1	0	0
修改后数据	-1	1	-1	-1	-1	1	1	-1	-1
前缀和	-1	0	-1	-2	-3	-2	-1	-2	-3

经过修改后的数据，假设 [l, r] 之前有 x 个元素，如果男生和女生数量一样多，必然这个 $\sum_{i=l}^{r}a_i$ ，即 sum[r] = sum[l-1]。

因此我们在计算前缀和的同时，建立一张哈希表，如上表所示，我们可以得到如下哈希表。

如上图所示，第一列数据为哈希表值，后面为对应哈希值的前缀和索引。我们可以看到以下几个信息：

1、前缀和为 0 只有一个数据，因此肯定无法组成男女组合。

2、前缀和为 -1 有三个数据，最小前缀和下标为 1，最大前缀和下标为 7，表明有 6 个人可以组成男女组合，即原数组下标 2 ~ 7 的数据，对应为 1 0 0 0 1 1，也就是 3 男 3 女。

3、前缀和为 -2 有三个数据，最小前缀和下标为 4，最大前缀和下标为 8，表明有 4 个人可以组成男女组合，即原数组下标 5 ~ 8 的数据，对应为 0 1 1 0，也就是 2 男 2 女。

4、前缀和为 -3 有两个数据，最小前缀和下标为 5，最大前缀和下标为 9，表明有 4 个人可以组成男女组合，即原数组下标 6 ~ 9 的数据，对应为 1 1 0 0，也就是 2 男 2 女。

AC 参考代码

暴力减枝实现

如果数据量超过 1e5，估计这个算法就力不从心了。部分要获得 TLE。

#include <cstdio> using namespace std; const int MAXN = 1e5+4; int nums[MAXN];//原始数据 int qzh[MAXN];//前缀和 int main() { int n; scanf("%d", &n); for (int i=1; i<=n; i++) { scanf("%d", &nums[i]); qzh[i] = qzh[i-1]+nums[i]; } /* i表示构造长度 j表示起点 */ int m= (1==n%2) ? n-1 : n; for (int i=m; i>=2; i-=2) { //n,n/2,n/4,...,4,2 的长度进行验证 for (int j=n; j-i>=0; j--) { if ((qzh[j]-qzh[j-i])*2==i) { printf("%d\n", i); return 0; } } } printf("0\n"); return 0; }

优化算法实现

我们知道 unordered_map 内部实现使用的是哈希表，所以我们可以使用 STL 的这个类型。

#include <cstdio> #include <unordered_map> using namespace std; const int MAXN = 1e5+4; int nums[MAXN];//前缀和 int main() { int n; scanf("%d", &n); unordered_map<int, int> hash; hash[0] = 0;//特例处理 int ans = 0; for (int i=1; i<=n; i++) { scanf("%d", &nums[i]); if (0==nums[i]) { nums[i] = -1; } nums[i] += nums[i-1];//构造前缀和 if (hash.find(nums[i]) == hash.end()) { //第一次出现，增加到哈希表中 hash[nums[i]] = i; } else if (i-hash[nums[i]]>0 && i-hash[nums[i]]>ans) { //出现过 ans = i-hash[nums[i]]; } } printf("%d\n", ans); return 0; }

使用 unordered_map，要注意一些特殊例子。如输入为

4 1 0 0 1

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/106303.html