글 읽기 - 공장 문제 질문입니다.

moonsoo5522 8년 전 0

두번째 배열에는 첫번째 배열 숫자의 인덱스를 매칭시켰습니다.

문제 테스트 케이스대로라면 순서는 2 - 4 - 1 - 3 - 5 이렇게 나왔구요.

펜윅트리를 사용해,

loop를 돌면서 i번째 인덱스의 경우에 (현재까지 연결시킨 전깃줄 갯수 - 현재까지 연결시킨 전깃줄에서, 현재 데이터 이하의 값의 누적합)으로 식을 짜서 돌렸습니다.

예를들어 현재 인덱스의 데이터가 3일 경우, (4 - sum(3))이라는 식을 세워서 자신보다 높은 수를 가진 데이터만 결과값에 더하는 식으로 짰는데

제출해보니 틀렸습니다;;

도와줘요 스피드백준....

#include <stdio.h>

int num[1000001];
int arr[500001];
int tree[500001];
int n;
int res;

int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= (i & -i);
    }
    return ans;
}
void update(int i, int re) {
    while (i <= n) {
        tree[i] += re;
        i += (i & -i);
    }
}
int main()
{
    scanf("%d", &n);
    int t;
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &t);
        num[t]=i;
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &t);
        arr[i]=num[t];
    }
    for(int i=1; i<=n; i++)
    {
        update(arr[i], 1);
        int ret = sum(arr[i]);
        res += (i-ret);
    }
    printf("%d", res);
}

moonsoo5522 8년 전 1

해결했습니다.

롱롱 쓰면 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

공장 문제 질문입니다.

moonsoo5522 8년 전 0

moonsoo5522 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말