Loading...

洛谷P1816 忠诚

check评论:0 条 remove_red_eye浏览量:397 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-05

此题可用倍增,线段树等多种问题求解,这里我说一下分块做法

首先是分块这种算法,时间复杂度是$O(\sqrt n)$ 级别的,不是很快也不是很慢 代码短最适合我这种懒人了

首先是如何分块

block=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    belong[i]=(i-1)/block+1;//每个数属于哪一块
    minn[belong[i]]=min(minn[belong[i]],a[i]);//每一块维护最小值
}

这一题只需要维护每一块最小值即可

而查询操作主要是这样的:

序列:1 2 3 4 5 
查询:[2,5]间最小值
可知1 2是一块,3 4是一块,5是一块
minn[1]=1,minn[2]=3,minn[3]=5//每块最小值
先查询第一个不完整的块[2,2],暴力查询最小值为2
再查询一个整块[3,4],最小值为minn[2]=3
最后查询不完整的快[5,5],暴力查询最小值为5
所以[2,5]最小值为2

查询代码:

int query(int x,int y)
{
    int minx=0x3f3f3f3f;
    for(int i=x;i<=min(belong[x]*block,y);i++)//处理左边不完整块
    {
        minx=min(minx,a[i]);
    }
    if(belong[x]!=belong[y])//如果不在同一块
    {
        for(int i=(belong[y]-1)*block+1;i<=y;i++)//处理右边不完整块
        {
            minx=min(minx,a[i]);
        }
    }
    for(int i=belong[x]+1;i<belong[y];i++)//处理完整块
    {
        minx=min(minx,minn[i]);
    }
    return minx;
}

最后上代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
int block;
int n,m;
int belong[100010],a[100010],minn[400];
int query(int x,int y)
{
    int minx=0x3f3f3f3f;
    for(int i=x;i<=min(belong[x]*block,y);i++)
    {
        minx=min(minx,a[i]);
    }
    if(belong[x]!=belong[y])
    {
        for(int i=(belong[y]-1)*block+1;i<=y;i++)
        {
            minx=min(minx,a[i]);
        }
    }
    for(int i=belong[x]+1;i<belong[y];i++)
    {
        minx=min(minx,minn[i]);
    }
    return minx;
}
main()
{
    memset(minn,0x3f3f3f3f,sizeof(minn));
    cin>>n>>m;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
        //cout<<"count "<<i<<":"<<minn[belong[i]]<<" "<<a[i]<<endl;
        minn[belong[i]]=min(minn[belong[i]],a[i]);
        //cout<<"count "<<i<<":"<<minn[belong[i]]<<" "<<a[i]<<endl;
    }
    /*for(int i=1;i<=5;i++)
    {
        cout<<minn[i];
    }*/
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld ",query(x,y));
    }
}
 

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名