当前位置:首页 > 数据结构 > 计蒜客 微软大楼设计方案(中等)

计蒜客 微软大楼设计方案(中等)

近日,微软新大楼的设计方案正在广泛征集中,其中一种方案格外引人注目。在这个方案中,大楼由 n栋楼组成,这些楼从左至右连成一排,编号依次为 1 到 n,其中第 i栋楼有 h_i 层。每栋楼的每一层为一个独立的 办公区域,可以步行 直达同层相邻楼栋的办公区域,以及 直达同楼栋相邻楼层的办公区域

由于方案设计巧妙,上一层楼、下一层楼、向左右移动到相邻楼栋同层的办公区域均刚好需要 1 分钟。在这些办公区域中,有一些被 核心部门 占用了(一个办公区域内最多只有一个核心部门),出于工作效率的考虑,微软希望核心部门之间的移动时间越短越好。对于一个给定的 最大移动时间 k,大楼的 协同值 定义为:有多少个 核心部门对 之间的移动时间不超过 k。由于大楼门禁的限制,不可以走出整个大楼,也不可以登上天台思考人生。你可以认为在办公区域内的移动时间忽略不计,并且在大楼内总是按照最优方案进行移动。

对于一个给定的新大楼设计方案,你能算出方案的协同值么?

输入格式

第一行包含两个正整数 n,k(1\leq k\leq 200020),分别表示大楼的栋数以及最大移动时间。

第二行包含 n 个正整数 h_1,h_2,...,h_n(1\leq h_i\leq 20),分别表示每栋楼的层数。

接下来一行包含一个正整数 m,表示 核心部门 个数。

接下来 m 行,每行两个正整数 x_i,y_i(1\leq x_i\leq n,1\leq y_i\leq h_{x_i}),表示该核心部门位于第 x_i 栋楼的第 y_i 层。

输入数据保证 m 个核心部门的位置不会重复。

对于简单版本:1\leq n,m\leq 50

对于中等版本:1\leq n\leq 200000,1\leq m\leq 2000

对于困难版本:1\leq n,m\leq 200000

输出格式

输出一个整数,即整个大楼的 协同值

样例解释

样例对应题目描述中的图,核心部门 1 和核心部门 3 之间的距离为 8>7,因此不能计入答案。

样例输入

5 7
4 1 1 3 1
3
1 4
3 1
4 3

样例输出

2

线段树

#include<stdio.h>
#include<algorithm>
using namespace std;

#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=200005;
int node[N<<2];
pair<int,int>pi[2005];


void pushup(int rt)
{
    node[rt]=min(node[rt<<1],node[rt<<1|1]);
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&node[rt]);
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}

int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        return node[rt];
    }

    int m=(l+r)>>1;
    int minn=0x3f3f3f3f;

    if(L<=m) minn=min(minn,query(L,R,lson));
    if(m<R) minn=min(minn,query(L,R,rson));

    return minn;
}

int main()
{
    int n,k,m,ans=0;
    scanf("%d %d",&n,&k);
    build(1,n,1);
    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d",&pi[i].fi,&pi[i].se);
    }
    for(int i=1; i<=m; i++)
        for(int j=i+1; j<=m; j++)
        {
            int x1,x2;
            x2=max(pi[i].fi,pi[j].fi);
            x1=min(pi[i].fi,pi[j].fi);
            int minn=query(x1,x2,1,n,1);
            if( min(pi[i].se,pi[j].se)<=minn )
            {
                if(k>=abs(pi[i].fi-pi[j].fi)+abs(pi[i].se-pi[j].se) )
                    ans++;
            }else {
                if(k>=pi[i].se+pi[j].se-2*minn+abs(pi[i].fi-pi[j].fi) )
                    ans++;

            }
        }
    printf("%d\n",ans);
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=457

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。