不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

在某个神奇的下午,收到一个垃圾邮件(至少被邮件系统当成了垃圾邮件)。

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

果然好久没碰算法,脑子是会生锈的。

第一题大水,懒得写。

第二题伤了很久的脑筋,想出了一个算法结果ultramanhu基于此想出了个更容易理解更容易实现的方法。

以我这种懒人的本性,必须是也懒得写得。

于是意思意思就干上了第三题。题目见这里 http://wenda60.com/programs/view/id-550.html

不得不说,现在不如从前,想出这题的解法还是费了一点时间的。不过这个题目太厚道了,能有的trick在sample里都有了。

这个题是问最少改多少个数字能让输入的数字递增,并且第一个数字不小于1。

很显然一个增子序列嘛。但是又有一点点地不同,应为最终是修改数字,而且数字不能重的,所以增子序列里两个相邻的值还和这两个数之间的数字个数有关。

就是这两个值的相差必须大于之间的数字个数。这里很容易就想到给最长增子序列变种,判断因素加上距离权值;

第二个条件是第一个值必须大于等于1。我想到的简单地做法是,在序列前面加一个0。轻松加愉快啊。

但是最长增子序列的算法是会重定向最佳值的,所以在执行检测的时候注意子序列一定要选0就OK了。

上代码:

#include <cstdio>
#include <iostream>

typedef int LISTYPE;

#define LISMAXN 100005

LISTYPE lR[LISMAXN];

int LIScmp(int a, int b, LISTYPE list[])
{
    return list[a] + b - a <= list[b];
}

int LISLength(LISTYPE list[], int n)
{
    int length = 1;
    
    lR[0] = 0;

    for (int i = 1; i < n; i++)
    {
        //二分查找,复杂度 log(n)
        int b, e, m;
        b = 0;
        e = length - 1;
        while (b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if (LIScmp(lR[m], i, list))
                b = m + 1;
            else
                e = m - 1;
        }

        if (0 == b) 
            continue;

        lR[b] = i;
        if (b >= length)
            length++;
    }
    return length;
}

LISTYPE LOri[LISMAXN];

int main() {
    int n;
    scanf("%d", &n);

    while (n-- > 0){
        int size;
        scanf("%d", &size);
        LOri[0] = 0;
        for (int i = 1; i <= size; ++i){
            scanf("%d", &LOri[i]);
        }

        printf("%d\n", size + 1 - LISLength(LOri, size + 1));
    }
    return 0;
}

不知道为什么,这个代码上去以后显示PE,我也不知道PE在哪了。(我试了各种乱加减空格和换行,都木有用,全PE。故意写错一个数,就变WA了,所以应该真的是PE) 不过反正结果对了后面就懒得再研究了,反正现在又不参赛

PS: 最长增子序列用得是以前写得模板:https://www.owent.net/2009/74.html

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(下)

一般来说,默认参数比方法族(method families)更可取,因为它减轻了 API 使用者的认知负担。

732
来自专栏小詹同学

【记录帖】(No.001)从零打卡刷Leetcode

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新...

1193
来自专栏程序员互动联盟

【专业技术】如何写出优美的C 代码?

面向对象的语言更接近人的思维方式,而且在很大程度上降低了代码的复杂性,同时提高了代码的可读性和可维护性,传统的 C 代码同样可以设计出比较易读,易维护,复杂度较...

3439
来自专栏前端布道

JavaScript 浮点数陷阱及解法

众所周知,JavaScript 浮点数运算时经常遇到会 0.000000001 和 0.999999999 这样奇怪的结果,如 0.1+0.2=0.300000...

2673
来自专栏ACM小冰成长之路

51Nod-1645-中位数变换

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

2117
来自专栏海天一树

Codeforces 976E 题解报告

http://codeforces.com/contest/976/problem/E

1283
来自专栏函数式编程语言及工具

泛函编程(0)-什么是泛函编程

 什么是泛函编程(Functional Programming)?泛函编程就是用函数编写程序。这个回答太抽象,等于没说。 再说清楚一点:泛函编程就想砌积木一样把...

2078
来自专栏Vamei实验室

Python基础08 面向对象的基本概念

Python使用类(class)和对象(object),进行面向对象(object-oriented programming,简称OOP)的编程。 面向对象的最...

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

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

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

1595
来自专栏数据结构与算法

群论入门

这东西一时半会儿写不完。。。 群 定义集合 ,*为集合G上的二元运算 当集合G在运算*之下满足一下性质时,我们称集合G在运算*之下是一个群,简称G是群 封闭性...

3545

扫码关注云+社区

领取腾讯云代金券