본문 바로가기

알고리즘 관련/BOJ

BOJ)2104 부분배열 고르기

문제: icpc.me/2104


주어지는 배열에서 i~j까지의 부분 배열을 선택했을 때 (a[i]+a[i+1]+...+a[j])*(min(a[i],a[i+1]),....,a[j]) 가 최대가 되도록 i j를 선택하는 문제이다.


나이브한 풀이법으로는 i,j를 선택하는데만 O(N^2)으로 시간초과다 ..


따라서 좀 더 그리디하게 생각해보면 만약에 어떤 구간에 대해 정할 때 한 점 X를 기준으로 그 점이 최솟값이 되게 구간을 선택한다면


X를 기준으로 좌우로 최대한 X보다 큰값을 가지는 범위롤 포함하도록 배열을 선택할 수 있다.


이러한 아이디어에서 출발하여 모든 점에 대해서 이 범위를 볼건데


정렬을 해주어 작은 값부터 보면서 set에 업데이트해주어 이동가능한 lower_bound와 upper_bound를 찾아준다면 O(NlongN)에 문제를 해결할 수 있다.


소스코드에서 set에 업데이트를 해줄 때 같은 값을 한번에 업데이트 시켜주기 위하여 업데이트 할 값을 queue에 저장해주었다. 


아 참고로 구간합은 당연히 psum을 이용하여 가져와줘야 한다.


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
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
set<ll> st;
queue<ll> qu;
ll n, a[100010], sum[100010], r, prv;
pair<ll, ll> p[100010];
int main() {
    scanf("%lld"&n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld"&a[i]);
        sum[i] = a[i] + sum[i - 1];
    }
    for (int i = 1; i <= n; i++)
        p[i] = { a[i],i };
    sort(p + 1, p + n + 1);
    prv = -1;
    for (int i = 1; i <= n; i++) {
        if (prv != p[i].second) {
            while (qu.size()) {
                st.insert(qu.front());
                qu.pop();
            }
        }
        if (!st.size()) {
            r = max(sum[n] * p[i].first, r);
            st.insert(p[i].second);
        }
        else {
            auto it = st.lower_bound(p[i].second);
            int lo, hi;
            if (it == st.end()) {
                it--;
                r = max((sum[n] - sum[*it])*p[i].first, r);
            }
            else {
                if (it == st.begin())
                    r = max(sum[*it - 1* p[i].first, r);
                else {
                    auto pit = it;
                    pit--;
                    r = max((sum[*it - 1- sum[*pit])*p[i].first, r);
                }
            }
        }
        qu.push(p[i].second);
    }
    printf("%lld\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2370 시장 선거 포스터  (1) 2017.08.21
BOJ)3073 집으로 가는 길  (0) 2017.08.21
BOJ)2872 우리집엔 도서관이 있어  (0) 2017.08.20
BOJ)10272 현상금 사냥꾼 김정은  (1) 2017.08.19
BOJ)8462 배열의 힘  (0) 2017.08.15