백준15824 너 봄에는 캡사이신이 맛있단다

작성일 | In

문제 링크

  • http://icpc.me/15824

사용 알고리즘

  • 정렬

풀이

가능한 모든 조합에 대해, (최댓값 - 최솟값)의 합을 구하는 문제입니다. N이 최대 30만까지 주어지기 때문에, 완전탐색으로 풀 수는 없습니다.

각각의 스코빌 지수(이하 x)에 대해, x가 최대가 되는 조합의 수와 x가 최소가 되는 조합의 수만 빠르게 알 수 있다면 정답을 쉽게 구할 수 있습니다.

먼저 정렬을 해줍시다. 정렬을 하게 되면 x보다 작은 수들은 모두 앞쪽, 큰 수들은 모두 뒤쪽으로 이동합니다.
x보다 작은 수가 i개 있다면, x가 최대가 되는 조합의 수는 2i인 것은 쉽게 알 수 있습니다.
x보다 큰 수가 j개 있다면, x가 최소가 되는 조합의 수는 2j입니다.

모든 x에 대해 x보다 작은 수가 i개, x보다 큰 수가 j개 있다면 (2i - 2j) * x의 합을 구해주면 됩니다.

거듭제곱은 O(log N)시간에 계산할 수 있기 때문에, O(N log N)만에 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n;
vector<ll> v;
const ll mod = 1e9+7;

ll pw(ll a, ll b){
	ll ret = 1;
	while(b){
		if(b & 1) ret = ret * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ret;
}

ll md(ll a, ll b){
	return ((a%b)+b)%b;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n);
	for(auto &i : v) cin >> i;
	sort(v.begin(), v.end());

	ll ans = 0;
	for(int i=0; i<n; i++){
		ll mxcnt = pw(2, i);
		ans += (v[i] % mod) * mxcnt % mod;
		ll mncnt = pw(2, n-i-1);
		ans -= (v[i] % mod) * mncnt % mod;
		ans = md(ans, mod);
	}
	cout << ans;
}