首页 > 试题广场 >

小苯的区间删除

[编程题]小苯的区间删除

热度指数：958 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小苯有一个长度为 $n$ 的数组 $a$ ，他想要使得数组 $a$ 有序（单调不降）。
为此，他必须选择一段区间 $[l, r], (1\leq l \leq r \leq n)$ ，将数组的这一段删除，其他的部分（如果存在的话）就按顺序拼在一起。

现在他想知道有多少种不同的选择区间的方案。

注：小苯认为，空数组也满足有序，即你可以选择 $[1,n]$ 这个区间。

输入描述:

输入包含两行。
第一行一个正整数 ，表示数组的长度。
第二行  个正整数 ，表示数组 。

输出描述:

输出一行一个正整数表示答案。

示例1

输入

3
1 2 3

输出

说明

可以选择：

这六个区间。

示例2

输入

5
1 3 2 2 5

输出

算法知识视频讲解

查看答案及解析

推荐

小小

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 2);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[n + 1] = 1e18;
    vector<int> p(n + 1), s(n + 2);
    for(int i = 1; i <= n; i++) {
        if(a[i] >= a[i - 1]) {
            p[i] = p[i - 1] + 1;
        }
        else {
            p[i] = 1;
        }
    }
    for(int i = n; i; i--) {
        if(a[i] <= a[i + 1]) {
            s[i] = s[i + 1] + 1;
        }
        else {
            s[i] = 1;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int x = a[i - 1];
        if(p[i - 1] < i - 1) break;
        int l = i, r = n + 1;
        while(l < r) {
            int mid = l + r >> 1;
            if(s[mid] == (n - mid + 1) && x <= a[mid]) r = mid;
            else l = mid + 1;
        }
        ans += n - l + 1;
        ans += l > i;
    }
    cout << ans << endl;
}


signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    while(_ -- ) {
        solve();
    }
    return 0;
}

编辑于 2025-02-18 17:09:48 回复(0)

Java

红红火火_

将序列分成[0,l] [r,n-1] 两个部分，这两个部分都是单调不减的，且nums[l] <= nums[r]。

左边的 l 枚举，右边的 r 用二分查找。

时间复杂度 o(nlogn）。

import java.util.Scanner;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0 ; i < n ; i++) {
            nums[i] = in.nextInt();
        }
        int ans = resolve(nums);
 
        System.out.println(ans);
        in.close();
    }
 
    private static int resolve(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return n;
        }
        boolean[] left = new boolean[n];
        boolean[] right = new boolean[n];
        left[0] = true;
        for(int i = 1; i < n && left[i-1]; i++){
            left[i] = nums[i] >= nums[i-1];
        }
 
        right[n-1] = true;
        int t = n - 1;
        for(int i = n - 2; i >= 0 && right[i+1]; i--){
            right[i] = nums[i] <= nums[i+1];
            if(right[i]){
                t = i;
            }
        }
        int ans = n - t + 1;
        for(int l = 0 ; l < n ; l++){
            if(!left[l]){
                break;
            }
            int r = getFirstLager(nums[l],nums,Math.max(l+1,t),n-1);
            ans += n - r + 1;
        }
        return ans;
    }
 
    private static int getFirstLager(int minValue,int[] nums , int left,int right){
        while(left <= right){
            int mid = ( left + right) >> 1;
            if(nums[mid] >= minValue){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

发表于 2025-03-06 19:28:30 回复(2)

Java

加麻加辣的猪猪很贪睡

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int length=in.nextInt();
        int[] array=new int[length];
        for(int i=0;i<length;i++) array[i]=in.nextInt();
        boolean[][] dp=new boolean[length][length];
        int ans=0;
        for(int f=length-1;f>=0;f--) {
            for(int l=0;l<length-f;l++) {
                int r=l+f;
                dp[l][r]=true;
                if((l>=1&&!dp[l-1][r])||(l>=2&&array[l-2]>array[l-1])||(r<=length-2&&!dp[l][r+1])||(r<=length-3&&array[r+1]>array[r+2])) dp[l][r]=false;
                // 上面两行可简化成 dp[r]= (l < 1 || dp[r]) && (l < 2 || array[l - 2] <= array[l - 1]) && (r > length - 2 || dp[r + 1]) && (r > length - 3 || array[r + 1] <= array[r + 2]);
                if(dp[l][r]) ans++;
            }
        }
        System.out.print(ans);
    }

给空间复杂度压缩到O(n)了都超空间，真有你的

编辑于 2025-02-14 21:56:11 回复(1)

提交观点

问题信息

数组双指针

来自：2024年春招-淘天集...

难度：

2条回答 57收藏 1925浏览

小苯的区间删除

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题