AcWing 1210. 连号区间数

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1210. 连号区间数原题链接简单

作者：

田所浩二 , 2019-12-13 21:48:36 , 所有人可见 , 阅读 11048

70

10

题目描述

题目描述就不在过多赘述但有一点需要注意给出的数组本身就涵盖了1-n的所有数，这里来讲一讲我的思路：
首先这个题需要理解这个连续性是什么，比如给你一个数组：1 3 5 4 2，然后我在里面随便去一段（取3 5 4）然后我把它排序（从小到大）发现也是3，4，5那就说明是连续的，除此之外当l=r时也算作连续
其次，想一下怎么做，这里设两层循环，一层i表示左端点，第二层j表示右端点。如果要保持连续性的话那么有一个思路：因为是连续的所以在所取的[l，r]范围中寻找最大值，最小值。然后相减，最后和r-l（区间长度）作比较即可。

样例

输入样例1：
4
3 2 4 1
输出样例1：
7

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=11000;
int a[N],ans=0;
int max1=0,min1=11000;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        max1=0;
        min1=11000;
        for(int j=i;j<=n;j++)
        {
           max1=max(a[j],max1);
           min1=min(a[j],min1);
           if((max1-min1)==(j-i))
           {
             ans++;
           }
        }
    }
    cout<<ans<<endl;
}

37 评论

边吃边敲 2022-03-26 11:29

//代码的优化历程
//①先双重for遍历所有区间–>对所有区间数字sort排序–>逐个判断每个数字是否比后面的数字小一
//②先双重for遍历所有区间–>对所有区间数字sort排序–>最大数减去最小数等于区间长度
//③先双重for遍历所有区间，同时求出Max和Min–>最大数减去最小数等于区间长度

繣濟 8个月前

牛的兄弟，谢谢！

xiaoyuer2815 2022-03-22 16:31

我又回来了，刚刚去提交有了点小困惑：数组下标从0开始，那么所选择的【l，r】区间的长度应该是r-l+1，所以再判断那个地方应该为：max1-min1==j-i+1，但是提交wa，想了想原来还是：max1-min1==j-i，比如，那个1、2、3（下标分别为0，1，2）举例，max1-min1=3-1=2，而j-i+1=3，明显不等，但是这个区间是符合的，所以即便数组下标从0开始应该还是max1-min1==j-i

Do2eM0N 2023-03-17 13:56

感谢，我也是这个疑惑。

者. 10个月前

这题解太臭了

Lukesu 2022-03-25 20:45

这思路真妙，我咋就想不到哩 Orz

大瓜娃子 2022-11-07 19:57

#题目所给的样例解释是数组下标(从1开始)
n = int(input())
arr = list(map(int,input().split()))

res = 0
for i in range(n):
    _max = arr[i]#区间(i,j)
    _min = arr[i]
    for j in range(i,n):
        if arr[j] > _max: _max = arr[j]
        if arr[j] < _min: _min = arr[j]
        if _max - _min == j -i: res += 1 #连续区间数组小技巧
print(res)

endeavor_1 2021-04-07 21:32

# 名字很嗯嗯嗯哼哼哼哼哼啊啊啊啊啊

菜勾一枚 1个月前

害，我看洛谷里的题解给我吓一跳

actp 8个月前

为什么不能用sort

._1322 9个月前

为什么不能把 l-r 的值传给从1开始的数组
···
#include[HTML_REMOVED]
using namespace std;
const int N=1e4+10;
int n;
int p[N];
int res=0;
bool check(int l,int r)
{
int t[N];
for(int i=1;i<=r-l+1;i)
{
t[i]=p[l];
l;
}
sort(t+1,t+1+r-l+1);
// memcpy(t,p,sizeof p);
// sort(t+l,t+r+1);
for(int i=1;i<r-l+1;i)
{
if(t[i+1]-t[i]!=1 )
{
return false;
}
}
return true;
}
signed main()
{
scanf(“%d”,&n);
for(int i=1;i<=n;i)
{
scanf(“%d”,&p[i]);
}
for(int i=1;i<=n-1;i)
{
for(int j=i+1;j<=n;j)
{
if(check(i,j))
{
res++;
}
}
}
int ans=res+n;
printf(“%d”,ans);
return 0;
}
···