即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

计蒜客2017 第六场 微软大楼设计办法(里等)

编程语言 qq_34287501 9℃ 0评论

题目链接:https://nanti.jisuanke.com/t/15772



解析:一个核心部门a位于楼L(高h1)到其他核心部门b位于楼R(高h2),求L~R的最小的高度h,然后最短路径为abs(R-L)+abs(h-h1)+abs(h-h2),关键问题就是一个RMQ

代码:

#include
#define N 200009
using namespace std;

int a[N], dp[N][33];

struct node
{
    int x, y;
}p[N];

bool cmp(node a, node b)
{
    return a.x < b.x;
}

void RMQ(int n)
{
    for(int j = 1; j != 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(i + (1<>1)][j-1]);
        }
    }
}

int main()
{
    int n, k, m, l, r;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        dp[i][0] = a[i];
    }
    RMQ(n);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    sort(p + 1, p + m + 1, cmp);
    int ans = 0;
    for(int i = 1; i <= m; i++)
    {
        l = p[i].x;
        for(int j = i + 1; j <= m; j++)
        {
            r = p[j].x;
            int kk = (int)(log(1.0*r-l+1) / log(2.0));
            int h = min(dp[l][kk], dp[r-(1<






转载请注明:CodingBlog » 计蒜客2017 第六场 微软大楼设计办法(里等)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情