牛客周赛39 --- G -- 小红不想做平衡树 -- 题解

小红不想做平衡树:

思路解析:

好数组的定义为 恰好翻转一个区间是得,这个区间变为升序的。

那么就有五种情况:

1.本身数组就升序的, 翻转一个长度为1的区间后,数组仍为升序

2.本身数组就降序的,翻转整个区间后,数组为升序。

3.数组先升序后降序,翻转降序区间后,数组变为升序 (需要满足降序区间最小元数大于升序区间最大元数)

4.数组先降序后升序,翻转降序区间后,数组变为升序,(需要满足降序区间最大元数小于升序区间最小元数)

5.数组先升序再降序后升序,翻转降序区间后数组变为升序,(需要满足3和4的条件)

代码实现:


import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
    static int inf = (int) 1e9;

    public static void main(String[] args) throws IOException {

        int t = 1;
        while (t > 0) {
            solve();
            t--;
        }
        w.flush();
        w.close();
        br.close();
    }

    static int n;
    static int[]  pre;
    static int[] suf;
    static int[] a;
    static long ans = 1;

    public static void solve() {
        n = f.nextInt();
        pre = new int[n+1];
        suf = new int[n+1];
        a = new int[n+1];
        for (int i = 1; i <= n; i++) {
            a[i] = f.nextInt();
        }

        pre[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (a[i] > a[i-1]) pre[i] = pre[i-1];
            else pre[i] = i;
            ans += i - pre[i] + 1;
        }
        suf[n] = n;
        for (int i = n-1; i > 0; i--) {
            if (a[i] < a[i+1] ) suf[i] = suf[i+1];
            else suf[i] = i;
        }
        int i = 1;
        while (i <= n){
            int j = i;
            while (j < n){
                if (a[j] > a[j+1]) j++;
                else break;
            }
            if (j > i) calc(i, j);
            i = j+1;
        }
        w.println(ans);
    }

    // 全升序
    // 全降序
    // 先升序后降序
    // 先降序后升序
    // 先升序, 后降序, 再升序

    public static void calc(int l, int r){
        int len = (r - l + 1);
        ans +=(long) len * (len - 1) / 2; // 全降序

        for (int i = l; i <= r; i++) { // 先升序 后降序
            if (a[i] <= a[l-1] || l == 1){
                break;
            }
            ans += l - pre[l];
        }
        ans -= l - pre[l];

        for (int i = r; i >= l; i--) { // 先降序 后升序
            if (a[i] >= a[r+1] || r == n) break;
            ans += suf[r] - r;
        }
        ans -= suf[r] - r;

        if (l > 1 && r < n && a[l] < a[r+1] && a[r] > a[l-1]){
            ans += (long) (l - pre[l]) * (suf[r] - r);
        }
    }

    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/528896.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

跨框架探索:React Redux 和 Vuex 对比分析快速掌握React Redux

React Redux 和 Vuex 都是前端状态管理库&#xff0c;分别用于 React 和 Vue.js 框架。 它们都提供了一套规范的状态管理机制&#xff0c;帮助开发者更好地组织和管理应用状态。下面是它们的一些异同点&#xff1a; 相同点&#xff1a; 中心化状态管理&#xff1a;两者都提…

环形链表 II - LeetCode 热题 26

大家好&#xff01;我是曾续缘&#x1f61b; 今天是《LeetCode 热题 100》系列 发车第 26 天 链表第 5 题 ❤️点赞 &#x1f44d; 收藏 ⭐再看&#xff0c;养成习惯 环形链表 II 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xf…

docker部署coredns服务器

创建文件夹 mkdir /coredns/config/添加一个CoreDNS配置文件 cat >/coredns/config/Corefile<<EOF.:53 {forward . 114.114.114.114:53log}EOF启动docker docker run -d --name coredns --restartalways \-v /coredns/config:/etc/coredns \-p 53:53/udp \regist…

HarmonyOS 开发-短视频切换实现案例

介绍 短视频切换在应用开发中是一种常见场景&#xff0c;上下滑动可以切换视频&#xff0c;十分方便。本模块基于Swiper组件和Video组件实现短视频切换功能。 效果图预览 使用说明 上下滑动可以切换视频。点击屏幕暂停视频&#xff0c;再次点击继续播放。 实现思路 使用Sw…

一文了解ERC404协议

一、ERC404基础讲解 1、什么是ERC404协议 ERC404协议是一种实验性的、混合的ERC20/ERC721实现的&#xff0c;具有原生流动性和碎片化的协议。即该协议可让NFT像代币一样进行拆分交易。是一个图币的互换协议。具有原生流动性和碎片化的协议。 这意味着通过 ERC404 协议&#xf…

混淆时,编译器优化导致通过反射赋值的类被清空问题

有几个反射赋值的类&#xff0c;之前一直是 keep 整个class的&#xff0c;现在要求对class的路径进行混淆。 当我启用混淆后&#xff0c;发现整个类的内容被清空了。 // 原始的类内容public class BaseLoadData {property("config_data1")public static String dat…

R语言数据可视化:ggplot2绘图系统

ggpolt2绘图系统被称为R语言中最高大上的绘图系统&#xff0c;使用ggplot2绘图系统绘图就像是在使用语法创造句子一样&#xff0c;把数据映射到几何客体的美学属性上。因此使用ggplot2绘图系统的核心函数ggplot来绘图必须具备三个条件&#xff0c;数据data&#xff0c;美学属性…

如何开始用 C++ 写一个光栅化渲染器?

光栅化渲染器是计算机图形学中最基础且广泛应用的一种渲染技术&#xff0c;它将三维模型转化为二维图像。下面我们将逐步介绍如何使用C语言从零开始构建一个简单的光栅化渲染器。 一、理解光栅化渲染原理 光栅化是一种将几何数据&#xff08;如点、线、三角形&#xff09;转换…

视频拍摄后如何用二维码分享?在线制作视频二维码的方法

现在很多人会将拍摄的视频内容用生成二维码的方式来分享给其他人&#xff0c;与以前使用微信、QQ、网盘等形式相比&#xff0c;二维码能够更加简单快捷的将视频传递给其他人查看&#xff0c;不需要下载缓存占用扫码者的内存&#xff0c;提供更好的用户体验效果。 视频转二维码…

大语言模型及提示工程在日志分析任务中的应用 | 顶会IWQoS23 ICPC24论文分享

本文是根据华为技术专家陶仕敏先生在2023 CCF国际AIOps挑战赛决赛暨“大模型时代的AIOps”研讨会闪电论文分享环节上的演讲整理成文。 BigLog&#xff1a;面向统一日志表示的无监督大规模预训练方法 BigLog: Unsupervised Large-scale Pre-training for a Unified Log Represen…

低代码平台适合谁用?业务岗能用它做什么?开发岗能用它做什么?一文讲清!

近期&#xff0c;低代码开发平台以其独特的魅力&#xff0c;迅速引发了大众的广泛关注。众多人士纷纷寻求了解各类低代码产品&#xff0c;以探究其功能与特点。 然而&#xff0c;有些人可能因一两款产品的体验不佳&#xff0c;便对整个低代码行业产生了偏见。但我要指出的是&am…

JS 表单验证

点击注册的时候&#xff0c;渲染出来&#xff0c;验证码是自动获取出来的 html&#xff1a; <div class"div1">用户名<input type"text" id"yhm"><span id"span1"></span><br>密码<input type"…

用AI作图,使用这个免费网站,快看我画的大鹏鸟和美女

还是大剑师兰特&#xff1a;曾是美国某知名大学计算机专业研究生&#xff0c;现为航空航海领域高级前端工程师&#xff1b;CSDN知名博主&#xff0c;GIS领域优质创作者&#xff0c;深耕openlayers、leaflet、mapbox、cesium&#xff0c;canvas&#xff0c;webgl&#xff0c;ech…

C语言面试题之判定字符是否唯一

判定字符是否唯一 实例要求 实现一个算法&#xff0c;确定一个字符串 s 的所有字符是否全都不同 实例分析 1、使用一个大小为 256 的bool数组 charSet 来记录字符是否出现过&#xff1b;2、遍历字符串时&#xff0c;如果字符已经在数组中标记过&#xff0c;则返回 false&a…

Linux、Docker、Brew、Nginx常用命令

Linux、Docker、Brew、Nginx常用命令 Linuxvi编辑器文件操作文件夹操作磁盘操作 DockerBrewNginx参考 Linux vi编辑器 Vi有三种模式。命令模式、输入模式、尾行模式&#xff0c;简单的关系如下&#xff1a; i -- 切换到输入模式&#xff0c;在光标当前位置开始输入文本。&a…

代码随想录算法训练营Day48|LC198 打家劫舍LC213 打家劫舍IILC337 打家劫舍III

一句话总结&#xff1a;前两题白给&#xff0c;第三题树形DP有点难。 原题链接&#xff1a;198 打家劫舍 滚动数组直接秒了。 class Solution {public int rob(int[] nums) {int n nums.length;int first 0, second nums[0];for (int i 2; i < n; i) {int tmp Math.m…

SysTick滴答定时器 - 延时函数

SysTick定时器 Systick定时器&#xff0c;是一个简单的定时器&#xff0c;对于CM3,CM4内核芯片&#xff0c;都有Systick定时器。Systick定时器常用来做延时&#xff0c;或者实时系统的心跳时钟。这样可以节省MCU资源&#xff0c;不用浪费一个定时器。比如UCOS中&#xff0c;分…

记录一次Ubuntu 22.04桌面版安装向日葵的过程

大概花了近一天的时间安装了WIN11和Ubuntu 22.04双系统&#xff0c;中间Ubuntu安装时出现了好几次失败&#xff0c;后来检查可能是下载的iso文件有问题&#xff0c;重新下载一次&#xff0c;刻录到U盘。安装才算成功。 最后的Ubuntu系统信息如下 接着安装向日葵的时候出错了&a…

visionOS 专门应用提交数大幅下降;Kimi 不断「吊打」国内各大厂 AI 模型丨 RTE 开发者日报 Vol.180

开发者朋友们大家好&#xff1a; 这里是 「RTE 开发者日报」&#xff0c;每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE &#xff08;Real Time Engagement&#xff09; 领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「…

【六 (3)机器学习-机器学习建模步骤/kaggle房价回归实战】

目录 文章导航一、确定问题和目标&#xff1a;1、业务需求分析&#xff1a;2、问题定义&#xff1a;3、目标设定&#xff1a;4、数据可行性评估&#xff1a;5、资源评估&#xff1a;6、风险评估&#xff1a; 二、数据收集&#xff1a;1、明确数据需求2、选择数据来源3、考虑数据…