데이터 구조 표 skyline

각 막대 그래프 는 3 원조 (Li, Hi, Ri) 로 표시 된다.그 중에서 Li 와 Ri 는 각각 막대 그래프 좌우 세로 선의 x 좌표 값 이 고 Hi 는 막대 그래프 의 높이 이다.예 를 들 어 위의 8 개의 막대 그래프 는 (1, 11, 5), (2, 6, 7), (3, 13, 9), (12, 7, 16), (14, 3, 25), (19, 18, 22), (23, 13, 29), (24, 4, 28) 로 나 타 났 다.막대 그래프 의 윤곽 은 윤곽 벡터 (V1, V2,..., Vm) 로 표시 할 수 있다.i 가 홀수 일 때 Vi 는 막대 그래프 윤곽 에 있 는 세로 선의 x 좌표 값 을 나타 낸다. i 가 짝수 일 때 Vi 는 막대 그래프 윤곽 에 있 는 가로 선의 높이 를 나타 낸다.
예 를 들 어 위의 그림 의 윤곽 벡터 는 (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0) 이다.
현재 점 을 주 는 n 개의 막대 그래프 에 대해 서 는 막대 그래프 의 윤곽 을 계산 합 니 다.
★ 데이터 입력
첫 번 째 줄 의 정수 n 은 n 개의 막대 그래프 (1 < = n < = 4000) 를 나타 낸다.
다음 n 줄 은 각 줄 에 3 개의 정수 (Li, Hi, Ri) 가 있 고 Li 와 Ri 는 각각 막대 그래프 좌우 세로 선의 x 좌표 값 이 며 Hi 는 막대 그래프 의 높이 (- 3000 < = Li, Ri < = 3000, 1 < = Hi < = 1000) 이다.
★ 데이터 출력
출력 계 산 된 막대 그래프 윤곽 벡터.
분석: 사실은 그림 에 따라 왼쪽 의 도형 을 오른쪽의 도형 으로 변환 하여 출력 할 때 인접 한 간격의 높이 가 다른 지 판단 하면 좌우 경계 에 마이너스 가 있 는 지 주의 할 수 있 기 때문에 더 해 야 한다. 그렇지 않 으 면 배열 이 경 계 를 넘 는 것 은 h < = 1000 n < = 4000 알고리즘 의 복잡 도가 O (nh) 이기 때문에 시간 을 초과 하지 않 는 다.
코드:

#include
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define INF 0X7fffffff
using namespace std;
const int maxn = 6e3 + 10;
int height[maxn];

// n n <= 4000
// li hi ri -3000 <= Li，Ri<= 3000， 1 <= Hi <= 1000



int main() {
     
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ms(height);
    for(int i = 0; i < n; i++) {
     
        int l, h, r;
        cin >> l >> h >> r;
        l += 3000;
        r += 3000;
        for(int i = l; i < r; i++) {
     
            if(h > height[i])
            height[i] = h;
        }
    }
    for(int i = 0; i < maxn - 1; i++) {
     
        if(height[i] != height[i + 1]) {
     
            cout << i - 2999 << " " << height[i + 1] << " ";
        }
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

낙 곡 P1637 3 원 상승 서브 시퀀스 (나무 모양 배열 인 데 나 는 블록 을 나 누 려 고 한다)

RT, 나무 모양 배열 스 포 문제, UVa 1428 과 유사 그러나 데 이 터 는 5e4 에 불과 해 물 한 덩어리 만 나 누 면 지나 간다. 사이즈 가 좀 더... 뭐 공부 해요?...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조 표 skyline

좋은 웹페이지 즐겨찾기