首页 > 试题广场 >

小苯的区间删除

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

热度指数：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)

他说他是自愿的

第一题强度就这么高，这道题改的吧：力扣 2972. 统计移除递增子数组的数目 II

发表于 2025-03-09 23:20:11 回复(1)

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)

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)

Python

Fansv587

n = int(input())
a = list(map(int, input().split()))
 
decrease_piont = []
 
for i in range(1,len(a)):
    if a[i]< a[i-1]:
        decrease_piont.append(i)
 
if decrease_piont == []:
    print (n * (n + 1) // 2)
    exit(0)
 
 
first_index = decrease_piont[0]
final_index = decrease_piont[-1]
 
wuhu = a[:first_index]
qifei = a[final_index:]
 
count = 0
for i in range(len(wuhu)+1):
    for j in range(len(qifei)+1):
        if i == len(wuhu)&nbs***bsp;j == len(qifei):
            count += 1
        else:
            if a[len(wuhu) - i - 1] <= qifei[j]:
                count += 1
print(count)

发表于 2025-03-05 15:04:04 回复(0)

牛客666655143号

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        st.parseNumbers();
        st.nextToken();
        int n = (int)st.nval;
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            st.nextToken();
            a[i] = (int)st.nval;
        }
        if(n == 1){
            System.out.println(1);
            return;
        }

        int left = 0; // record the longest sorted list from left
        int right = a.length - 1; // record the longest sorted list from right
        while(left < n - 1 && a[left] <= a[left + 1]){
            left++;
        }
        while(right > 0 && a[right] >= a[right - 1]){
            right--;
        }
        if(left >= right){
            System.out.println(n * (n + 1) / 2);
            return;
        } else {
            int result = 0;
            for (int i = 0; i <= left + 1; i++) {
                for (int j = right - 1; j < n; j++) {
                    if (i == 0 || j == n - 1 || a[i - 1] <= a[j + 1] ) {
                        result++;
                    }
                    
                }
            }
            System.out.println(result);
        }


    }
}

发表于 2025-02-24 20:21:26 回复(0)

哇哈哈asd

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }

        // 双指针，[0, i]表示前缀数组 [j, n - 1]表示后缀数组
        int i = 0, j = n - 1;
        while(i < n - 1 && a[i] <= a[i + 1]) {
            i++;
        }
        if(i == n  - 1) { // 数组全部单调不降
            System.out.println(1L * n * (n + 1) / 2);
            return;
        }

        long ans = i + 2; // 不留后缀的情况
        while(j == n - 1 || a[j] <= a[j + 1]) {
            while(i >= 0 && a[i] > a[j]) {
                i--;
            }
            ans += i + 2;
            j--;
        }
        System.out.println(ans);
    }
}

发表于 2025-04-23 15:42:10 回复(0)

英俊的秋田犬说等下个版本吧

这道题是不是求有多少递增序列的反过来思考啊？给定数组长度,那么分割方法就确定了只要减去递增序列的个数就是排列的个数

发表于 2025-03-12 11:26:29 回复(1)

一笑而过2222

代码如下

发表于 2025-03-11 11:37:46 回复(1)

提交观点

问题信息

数组双指针

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

难度：

9条回答 56收藏 1920浏览

小苯的区间删除

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题