MT2049 运动会进行中

简介: MT2049 运动会进行中

a5adf76415d5456c9811a65c51fac8b1.jpg

思路:使用a存前缀和。遇见女生-1,遇见男生+1。之后遍历a的时候,如果a[i]=a[j],则说明ij这个区间里男女生数量是一样的。所以即求ij这个区间最大长为多少。可以用l[]r[]数组记录某个数第一次出现的位置和最后一次出现的位置。

例如样例:a[]=-1 0 -1 -2 -3 -2 -1 -2 -3

l[-1]=1     r[-1]=7

l[0]=2      r[0]=2

l[-2]=4      r[-2]=6

l[-3]=5     r[-3]=9

所以答案为7-1=6

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, sum[N], l[N * 2], r[N * 2], ans;
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> m; // 0女1男
        if (m == 0)
        {
            sum[i] = sum[i - 1] - 1;
        }
        else
        {
            sum[i] = sum[i - 1] + 1;
        }
        int tmp = sum[i] + n; // sum[i]的范围是-n到n,矫正保证为正数
        if (l[tmp] == 0)
        {
            l[tmp] = i;
        }
        else
        {
            r[tmp] = i;
        }
    }
    for (int i = 0; i < 2 * n; i++)
    {
        ans = max(ans, r[i] - l[i]);
    }
    cout << ans;
    return 0;
}


相关文章
|
SQL 分布式计算 Ubuntu
基于Hadoop的数据仓库Hive安装
基于Hadoop的数据仓库Hive安装
591 0
|
缓存 负载均衡 网络协议
Hapoxy-集群服务搭建
Hapoxy-集群服务搭建
200 1
Hapoxy-集群服务搭建
|
测试技术 Linux 持续交付
Docker笔记1 | Docker学习和简介
Docker笔记1 | Docker学习和简介
263 0
|
JavaScript 前端开发
万文篇章带你搞懂JavaScript——如何使用js实现模态框拖动,放大镜和侧边栏固定效果
万文篇章带你搞懂JavaScript——如何使用js实现模态框拖动,放大镜和侧边栏固定效果
318 0
万文篇章带你搞懂JavaScript——如何使用js实现模态框拖动,放大镜和侧边栏固定效果
|
自然语言处理 人工智能 知识图谱
SIGIR2019 | 你调用智能客服的那一刻,支付宝AI都做了哪些工作?
SIGIR是展示信息检索领域新技术和新成果的顶级国际会议。今年支付宝共有多篇论文入选,本文将重点介绍本次支付宝入选的论文成果精华。
1588 0
SIGIR2019 | 你调用智能客服的那一刻,支付宝AI都做了哪些工作?
|
敏捷开发 测试技术
敏捷开发管理--任务分解经验之谈
敏捷开发中怎样做好任务分解?
2787 0
|
Web App开发 关系型数据库 Java
Spring Boot入门(4)提交表单并存入MySQL数据库
项目介绍   在前两篇博客: Spring Boot入门(2)使用MySQL数据库和Spring Boot入门(3)处理网页表单中,我们已经掌握了如何在Spring Boot中操作MySQL数据库以及网页中的表单。
2352 0
H264 NALU 使用PS封装 RTP发送
最近由于项目平台需求,要将H264 NALU封装为PS再用RTP发送,PS封装按照ISO DEC-13818-1标准。一个PS包包含PS Header, PES Header, PS system header, PS system map等。
2222 0