首页 > 试题广场 >

小苯的区间删除

[编程题]小苯的区间删除
  • 热度指数：1331 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小苯有一个长度为 n 的数组 a，他想要使得数组 a 有序（单调不降）。
为此，他必须选择一段区间 [l, r], (1\leq l \leq r \leq n)，将数组的这一段删除，其他的部分（如果存在的话）就按顺序拼在一起。
现在他想知道有多少种不同的选择区间的方案。

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

输入描述:
输入包含两行。
第一行一个正整数 n, (1 \leq n \leq 2 \times 10^5)，表示数组的长度。
第二行 n 个正整数 a_i, (1 \leq a_i \leq 10^9)，表示数组 a。


输出描述:
输出一行一个正整数表示答案。
示例1

输入

3
1 2 3

输出

6

说明

可以选择：
[1, 1], [2,2],[3,3],[1,2],[2,3],[1,3]
这六个区间。
示例2

输入

5
1 3 2 2 5

输出

10
算法知识视频讲解
添加回答
推荐
小小头像 小小 
#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)
JavaScript
没电的皮卡丘_onlywin头像 没电的皮卡丘_onlywin
const rl = require("readline").createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value?.trim();

void (async function () {
    let n = parseInt(await readline());
    let a = (await readline()).split(/\s+/).map(Number);
    const result = function (n, a) {
        let left = 0;
        let right = n - 1;
        while (left < n && a[left] <= a[left + 1]) left++;
        if (left == n - 1) return (n * (n + 1)) / 2;
        while (right > 0 && a[right] >= a[right - 1]) right--;
        let sum = n - right + 1;
        let j = right;
        for (let i = 0; i <= left; i++) {
            while (j < n && a[i] > a[j]) {
                j++;
            }
            sum += n - j + 1;
        }

        return sum;
    };
    console.log(result(n, a));
})();
发表于 2026-04-03 23:50:08 回复(0)
提交观点

问题信息

数组 双指针
来自：2024年春招-淘天集...
难度：
1条回答 3094浏览

热门推荐

相关试题

小苯的区间删除

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号