1015 天际轮廓

Myth丶恋晨 2022-09-11 15:21 176阅读 0赞

**Description**

给定N(N<=50000)栋建筑物左右边界坐标及高度，输出这N栋建筑物天际轮廓的形状变化. 输入示例如下图所示.

![5d17a7a7fa2768e788170964cd7af801.png][]

**Input**

第一行输入N表示有N栋建筑物，接下来N行每行输入三个int型整数a、b、h，分别表示每栋建筑物的左右边界坐标和高度.

**Output**

输出若干行，每行输出两个数x、h，表示天际轮廓在坐标x处高度发生变化，变化为h.

**Sample Input**

8
    1 5 11
    2 7 6
    3 9 13
    12 16 7
    14 25 3
    19 22 18
    23 29 13
    24 28 4

**Sample Output**

1 11
    3 13
    9 0
    12 7
    16 3
    19 18
    22 3
    23 13
    29 0
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    struct build_t {
        int a,b,h;
    } build[50001];
    struct height_t {
        int a, h;
    } ht[50001*2], temp[50001*2];
    int n;
    
    int cmp_build (const void * a, const void * b) {
        return ((build_t *)a)->a - ((build_t *)b)->a;
    }
    int cmp_height (const void * a, const void * b) {
        build_t *c = (build_t *)a;
        build_t *d = (build_t *)b;
        if(c->a != d->a) {
            return c->a - d->a;
        }
        else {
            return c->h - d->h;
        }
    }
    
    int remove(int s, int e) {
        int k = s;
        for(int i=s+1; i<e; i++) {
            if(ht[i].a == ht[k].a) {
                if(ht[k].h < ht[i].h) {
                    ht[k] = ht[i];
                }
            }
            else if(ht[k].h != ht[i].h) {
                k++;
                ht[k] = ht[i];
            }
        }
        return k-s+1;
    }
    
    int merge(int low, int lenleft, int mid, int lenright) {
        int i=low;
        int j=mid;
        int k=low;
        int curh = 0;
        int lh = 0;
        int rh = 0;
        for(; i<low+lenleft; i++) {
            for(; j<mid+lenright; j++) {
                if(ht[i].a == ht[j].a) {
                    temp[k] = ht[i].h>ht[j].h ? ht[i] : ht[j];
                    k++;
                    lh = ht[i].h;
                    rh = ht[j].h;
                    
                    i++;                
                    if(i>=low+lenleft) {
                        j++;
                        break;
                    }
                }
                else if(ht[i].a < ht[j].a) {
                    temp[k].a = ht[i].a;
                    temp[k].h = ht[i].h>rh ? ht[i].h : rh;
                    k++;
                    lh = ht[i].h;
                    break;
                }
                else {
                    temp[k].a = ht[j].a;
                    temp[k].h = ht[j].h>lh ? ht[j].h : lh;
                    k++;
                    rh = ht[j].h;
                }
            }
            if(j >= mid+lenright) {
                break;
            }
        }
        for(; i<low+lenleft; i++) {
            temp[k].a = ht[i].a;
            temp[k].h = ht[i].h;
            k++;
        }
        for(; j<mid+lenright; j++) {
            temp[k].a = ht[j].a;
            temp[k].h = ht[j].h;
            k++;
        }
        for(i=low; i<k; i++) {
            ht[i] = temp[i];
        }
        return remove(low, k);
    }
        
    int divide(int low, int high, int depth) {
        if(low > high) {
            return 0;
        }
        if(low == high) {
            ht[2*low].a = build[low].a;
            ht[2*low].h = build[low].h;
            ht[2*low+1].a = build[low].b;
            ht[2*low+1].h = 0;
            return 2;
        }
        int mid = (low+high)/2;
        int lenleft = divide(low, mid, depth+1);
        int lenright = divide(mid+1, high, depth+1);
        qsort(&ht[2*low], lenleft, sizeof(height_t), cmp_height);
        qsort(&ht[2*(mid+1)], lenright, sizeof(height_t), cmp_height);
        
        int res = merge(2*low, lenleft, 2*(mid+1), lenright);
        
        return res;
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%d%d%d", &build[i].a, &build[i].b, &build[i].h);
        }
        qsort(build, n, sizeof(build_t), cmp_build);
        int len = divide(0, n-1, 0);
        for(int i=0; i<len; i++) {
            printf("%d %d\n", ht[i].a, ht[i].h);
        }
        return 0;
    }

[5d17a7a7fa2768e788170964cd7af801.png]: /images/20220828/c84f2f3f8ee545b4a2e3f75c6ab6f8a4.png