안녕하세요. 오늘은 줄을 설 거예요.
문제
https://www.acmicpc.net/problem/27897
아이디어
최대한 내림차순으로 정렬되게 만들어야합니다.
정확히는 A[i]>A[j]이고 i<j인 쌍이 최대한 많아야합니다.
하지만 인접한것 끼리만 바꿀 수 있으므로 한번의 교환에서 저 쌍의 개수는 한개가 늘거나, 일정하거나, 한개가 줄어들게 되어있습니다.
그런데 여기서 중요한 포인트를 잡을 수 있습니다. 바로 저 수열이 내림차순이 아닌 이상 무조건 저 값이 1 증가하도록 하는 쌍이 있다는 것입니다. 그래서 초기 상태에서 저 쌍의 개수를 K라고 하면 이후 L번을 더 바꿨을때 최대 K+L개의 쌍이 생긴다는 것입니다.
여기서 주의할 점이 있습니다.
바로 쌍의 개수 그 자체인데요, N개의 수에서 나올 수 있는 최대의 쌍의 개수는 N(N-1)/2로 정답은 min(K+L,N(N-1)/2)가 됩니다. 이 K값은 세그트리로 간단히 해결할 수 있습니다.
혹시 세그트리로 어떻게 하는지 모르시는 분들을 위해 설명하자면
인덱스 1부터 순서대로 확인한다.
앞에서 자기보다 큰 수의 개수를 센다.
이때 값에 대해서 세그먼트 트리를 쓸건데 수의 범위는 [1,N]이므로 자신이 x이면 앞에 있던 수들중에 [x+1,N]에 포함되는 수의 개수를 세어주면 됩니다.
자신을 체크한다.
이 순서를 그대로 하면 됩니다.
소스코드
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll tree[2020202] = { 0 };
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
if (e < l || r < s) return 0;
if (l <= s && e <= r) return tree[node];
ll mid = (s + e) / 2;
return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll idx)
{
if (e < idx || idx < s) return;
tree[node]++;
if (s == e) return;
ll mid = (s + e) / 2;
change(s, mid, node * 2, idx);
change(mid + 1, e, node * 2 + 1, idx);
}
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll N, L, i, ans = 0, x;
cin >> N >> L;
for (i = 1; i <= N; i++)
{
cin >> x;
ans += SUM(1, N, 1, x + 1, N);
change(1, N, 1, x);
}
cout << min(N * (N - 1) / 2, ans + L);
}
감사합니다.
