글 읽기 - 분할정복으로 풀이를 생각했는데 틀린 케이스 부탁드리겠습니다.

ybs1164 2년 전 0

일단 오름차순으로 정렬한 뒤에

분할 정복으로 풀이를 생각해봤습니다.

두 집합이 있다면 왼쪽에서 최소값, 오른쪽에서 최대값을 구하는 경우를 생각한 뒤에

최대값들을 기준으로 최소값들을 아래와 같이 더해줬습니다.

어디가 틀렸는지 잘 모르겠습니다.. 틀린 곳이나 케이스를 알려주신다면 감사하겠습니다.

#include <stdio.h>
#include <algorithm>
using namespace std;

int n;
long long a[300001];

long long f(int s, int e){
    int m = (s + e) / 2;
    
    if (s<e){
        long long sum=0, min_sum=0, t=1, tt=0;
        for (int i=m;i>=s;i--){
            min_sum += a[i] * t % 1000000007;
            min_sum %= 1000000007;
            tt += t;
            tt %= 1000000007;
            t *= 2;
            t %= 1000000007;
        }
        t = 1;
        for (int i=m+1;i<=e;i++){
            sum += (a[i]*tt - min_sum) % 1000000007 * t;
            sum %= 1000000007;
            t *= 2;
            t %= 1000000007;
        }
        return (sum+f(s, m)+f(m+1, e))%1000000007;
    } else {
        return 0;
    }
}

int main(){
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        scanf("%lld",&a[i]);
        a[i] %= 1000000007;
    }
    sort(a, a+n);

    printf("%lld",f(0, n-1));
    
    return 0;
}

ybs1164 2년 전 0

해결했습니다!

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

문제

문제

출처

ICPC

분할정복으로 풀이를 생각했는데 틀린 케이스 부탁드리겠습니다.

ybs1164 2년 전 0

ybs1164 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말