51Nod-1645-中位数变换

ACM模版

描述

题解

这个题很明显是找规律的问题,直接暴力肯定会超时……虽然我也是暴力也两发才反应过来……平时做题总是抱着侥幸心理,比赛时却总是胆小如鼠……

自己手解几组长一点的数据就可以发现,不管初始状态如何,最终都会变成连续的 00 和连续的 11 的若干组合,这里的连续是长度大于 11。那么,换言之也就是所有的 00 和 11 紧密交替子序列会被格式化,最后格式化成什么呢?

经过推算发现,最后的格式和这个子序列的长度的奇偶性有关, 如果是奇数,最后的格式要么全是 00,要么全是 11,决定因素是这个子序列的第一个元素的值; 如果是偶数的话,最后的格式要么是一半 00、一半 11,要么是一半 11、一半 00,决定因素是这个序列的首尾元素的值。

如此这般,最终需要执行的次数肯定是满足上述要求的最长的子序列操作的次数。对于每一个子序列假如长度为 lenlen,那么它需要操作的次数为 (len−1)>>1(len - 1) >> 1。

GG,这个题也就顺利 ACAC 了,不难做,就是需要细心发现规律才行,代码很容易理解的。由于我又加入了输入外挂,所以效率一下子升到了第一,棒极了。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int n;
int a[MAXN];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    scan_d(n);
    for (int i = 1; i <= n; i++)
    {
        scan_d(a[i]);
    }

    a[n + 1] = a[n];
    int len = 1, ans = 0, l = 1, r = 1;
    for (int i = 2; i <= n + 1; i++)
    {
        if (a[i] != a[i - 1])
        {
            r = i;
            len++;
        }
        else
        {
            ans = max(ans, (len - 1) >> 1);
            if (len & 1)
            {
                for (int j = l; j <= r; j++)
                {
                    a[j] = a[l];
                }
            }
            else
            {
                int mid = (l + r) >> 1;
                for (int j = l; j <= r; j++)
                {
                    a[j] = j <= mid ? a[l] : a[r];
                }
            }
            len = 1;
            l = r = i;
        }
    }

    printf("%d\n%d", ans, a[1]);
    for (int i = 2; i <= n; i++)
    {
        putchar(' ');
        putchar('0' + a[i]);

    }
    putchar(10);

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏进击的程序猿

进击算法:字符串匹配的 BM 算法

各种文本编辑器的 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。

2773
来自专栏zaking's

js算法初窥03(搜索及去重算法)

1292
来自专栏互联网技术栈

设计模式- 合成/组合原则

上面的问题都来源于对方法的改写动作。如果你在扩展一个类的时候,仅仅是增加新的方法,而不改写已有的方法,你可能会认为这样做是安全的,但是也并不是完全没有风险。

1124
来自专栏专注数据中心高性能网络技术研发

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

3439
来自专栏Danny的专栏

面向对象三大特征

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1962
来自专栏ACM算法日常

Dijkstra(单源最短路径)-PKU1062

图论中另一个求最小生成树的的经典算法Prim算法与Dij过程极其类似,都是贪心思想。只是一个是对顶点的选择,另外一个是对边的选择。

1402
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(01-05打卡)

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。

1595
来自专栏数据分析

[数据清洗]-看上去一样的数字

数据不正确(格式不正确,数据不准确,数据缺失)我们做什么都是徒劳。数据清洗时数据分析的第一步,也是最耗时的一步。 数据清洗很枯燥,但是随着数据清理技巧越来越熟练...

2873
来自专栏编舟记

函数式编程简介

1900年,Hilbert 提出了数学界悬而未决的10大问题,后续陆续添加成了23个问题,被称为著名的 Hilbert 23 Problem。针对其中第2个决定...

1984
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之高效、简洁的编码技巧“递归”

盗梦空间想象大多数人都看过:电影讲述的是主人公诺兰进入希里安·墨菲梦境植入想法的行动。为了向希里安·墨菲梦植入理念,影片进入四层梦境,即所谓:“梦中的梦中 梦中...

1153

扫码关注云+社区

领取腾讯云代金券