首页 > 试题广场 >

小苯的区间删除

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

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

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)