AcWing 초고 속 정렬

AcWing 초고 속 정렬
Description
  • 이 문제 에서 특정한 정렬 알고리즘 - 초고 속 정렬 을 분석 해 야 합 니 다.이 알고리즘 은 두 개의 인접 한 서열 요 소 를 교환 하여 n 개의 서로 다른 정수 서열 을 처리 하고 서열 이 오름차 순 으로 정렬 될 때 까지 처리 합 니 다.입력 시퀀스 9 1 0 5 4 에 대해 초고 속 정렬 생 성 출력 0 1 4 5 9.초고 속 정렬 이 얼마나 많은 교환 작업 을 수행 해 야 주어진 입력 순 서 를 정렬 할 수 있 는 지 확인 하 는 것 이 작업 입 니 다.

  • Input
  • 입력 은 테스트 용례 를 포함한다.모든 테스트 용례 의 첫 줄 에 정수 n 을 입력 하면 이 용례 에서 입력 한 서열 의 길 이 를 대표 합 니 다.다음 n 줄 마다 정수 ai 를 입력 하고 사례 에서 서열 의 구체 적 인 데 이 터 를 입력 하 며 i 줄 의 데이터 대표 서열 에서 i 번 째 수 를 입력 합 니 다.입력 용례 에 포 함 된 입력 시퀀스 길이 가 0 일 때 입력 이 종료 되 며 이 시퀀스 는 처리 할 필요 가 없습니다.

  • Output
  • 처리 해 야 할 모든 입력 시퀀스 에 대해 하나의 정수 op 을 출력 하 는 것 은 주어진 입력 시퀀스 에 대해 정렬 하 는 데 필요 한 최소 교환 조작 수 를 나타 내 고 모든 정수 가 한 줄 을 차지 하 는 것 을 의미한다.

  • Sample Input
    5
    9
    1
    0
    5
    4
    3
    1
    2
    3
    0

    Sample Output
    6
    0
    Data Size
  • 0≤N<500000, 0≤ai≤999999999

  • 문제 풀이:
  • 인접 원 소 를 교환 하 는데............................................................
  • 그럼 교환 횟수 는 역순 대 개수 군요.yy 는 단번에 이해 하기 쉽다.
  • 저 는 나무 모양 의 배열 로 역 서 를 구 합 니 다.몇 가지 주의해 야 할 점:
  • 나무 모양 의 배열 로 반드시 이산 화 되 어야 한다... 공간 폭격 시간
  • 중복 되 는 숫자 가 있 으 면 어떻게 합 니까?괜 찮 습 니 다. 발견 되 었 습 니까? 업데이트 할 때 + 1 이지 = 1
  • 이 아 닙 니 다.
    #include 
    #include 
    #include 
    #include 
    #define N 500005
    #define lowbit(x) (x & (-x))
    #define LL long long
    using namespace std;
    
    LL n, cnt, ans;
    LL a[N], b[N], c[N];
    
    LL read()
    {
        LL x = 0; char c = getchar();
        while(c < '0' || c > '9') c = getchar();
        while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
        return x;
    }
    
    LL ask(LL pos)
    {
        LL r = 0;
        while(pos >= 1)
        {
            r += c[pos];
            pos -= lowbit(pos);
        }
        return r;
    }
    
    void update(LL pos, LL val)
    {
        while(pos <= n)
        {
            c[pos] += val;
            pos += lowbit(pos);
        }
    }
    
    LL find(LL x) {
        return lower_bound(b + 1, b + 1 + cnt, x) - b;
    }
    
    int main()
    {
        while(scanf("%lld", &n) == 1)
        {
            if(!n) break;
            ans = cnt = 0;
            memset(c, 0, sizeof(c));
            for(LL i = 1; i <= n; i++) a[i] = read(), b[++cnt] = a[i];
            sort(b + 1, b + 1 + cnt);
            cnt = unique(b + 1, b + 1 + cnt) - b - 1;
            for(LL i = 1; i <= n; i++)
            {
                LL t = find(a[i]);
                update(t, 1);
                ans += (i - ask(t));
            }
            printf("%lld
    ", ans); } return 0; }

    다음으로 전송:https://www.cnblogs.com/BigYellowDog/p/11273998.html

    좋은 웹페이지 즐겨찾기