Peienwu's Blog

Hello world

0%

[題解]APCS幸運數字

發表於 分類於 Valine：
文章字數： 4.3k 所需閱讀時間 ≈ 4 分鐘

P3 幸運數字

題目連結

以區間最小值作為區分點將數列分成兩半，可以利用線段樹找區間最小值，利用迴圈模擬每一次範圍縮小的情況。

不過這一題比較特別，他的區間範圍一定會越來越小，且區間外的數字也就不需要使用到，因此可以將數列做一次排序，從頭開始找如果遇上區間外的數字則不理他，否則使用它當作區間的分隔點（這一定會是最小值，因為由小到大排序），將區間範圍縮小。

至於挑選左右區間的區間和，則可以透過前綴和 $O(1)$ 算出答案。

時間複雜度： 如果是一個遞增或遞減的序列，則每一次區間大小只會縮減1，此時複雜度為 $O(n)$，加上最一開始的排序是 $O(n\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 ll long long
#define ld long double
#define int long long
#define N 300005
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,arr[N],pref[N];
pii sorted[N];

signed main(){
    Orz;
    cin>>n;
    rep(i,1,n){
        cin>>sorted[i-1].x;
        arr[i] = sorted[i-1].x;
        sorted[i-1].y = i;
        pref[i] = pref[i-1]+arr[i];
    }
    sort(sorted,sorted+n);

    int ind = 0,l = 1,r = n;

    while(r>l){
        while(sorted[ind].y > r || sorted[ind].y < l)ind++;
        int left = pref[sorted[ind].y-1]-pref[l-1];
        int right = pref[r]-pref[sorted[ind].y];
        if(left > right){
            r = sorted[ind].y-1;
        }
        else{
            l = sorted[ind].y+1;
        }
    }
    cout<<arr[l]<<endl;
}

線段樹作法

如果用線段樹實作，尋找區間最小值，可以在 $O(\log n)$ 的時間內詢問。在最差的情況下，一共會詢問 $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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define N 300005
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,arr[N],pref[N];
pii seg[4*N];

//建立線段樹[l,r)
void build(int cur,int l,int r){
    if(r <= l)return;
    if(r - l <= 1){
        seg[cur] = {arr[l],l};
        return;
    }
    int mid = (l+r)/2;
    build(2*cur,l,mid);
    build(2*cur+1,mid,r);
    if(seg[2*cur].x < seg[2*cur+1].x)
        seg[cur] = seg[2*cur];
    else
        seg[cur] = seg[2*cur+1];
}

//詢問區間最小值，回傳pair
pii query(int cur,int l,int r,int ql,int qr){
    if(r <= l || ql >= r || qr <= l)return {INT_MAX,INT_MAX};
    if(ql <= l && qr >= r)return seg[cur];
    int mid = (l+r)/2;
    pii lft = query(2*cur,l,mid,ql,qr);
    pii rgt = query(2*cur+1,mid,r,ql,qr);
    if(lft.x < rgt.x)return lft;
    return rgt;
}

signed main(){
    Orz;
    cin>>n;
    rep(i,1,n){
        cin>>arr[i];
        pref[i] = pref[i-1]+arr[i];
    }
    build(1,1,n+1);
    int l = 1,r = n+1;
    
    while(r - l > 1){
        int ind = query(1,1,n+1,l,r).y;
        int left = pref[ind-1] - pref[l-1];
        int right = pref[r-1] - pref[ind];
        if(left > right)r = ind;
        else l = ind + 1;
    }
    cout<<arr[l]<<"\n";
}

歐恩作法

BY thanksone

有一種二元樹，我也不知道叫啥，根為全序列最小值，左節點為左邊序列最小值，右節點為右邊序列最小值。

建法

紀錄每個位置左、右邊離自己最近、比自己小的，爸爸就是兩個之中比較大的那一個。

時間複雜度： 種樹加跑答案總共 $O(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
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
array<int, 300004> A, S, L, R;
array<pii, 300004> tree;
void plant(int n){
    for(int i = 1; i <= n; i++){
        if(A[L[i]] > A[R[i]]) tree[L[i]].ss = i;
        else tree[R[i]].ff = i;
    }
}
int solve(int l, int r, int m){
    if(l == r) return A[l];
    if(S[m - 1] - S[l - 1] > S[r] - S[m]) return solve(l, m - 1, tree[m].ff);
    else return solve(m + 1, r, tree[m].ss);
}
signed main(){
    int n;
    cin >> n;
    stack<pii> s;
    pii m = {1e9, 0};
    s.push({0, 0});
    for(int i = 1; i <= n; i++){
        cin >> A[i];
        if(A[i] < m.ff) m = {A[i], i};
        S[i] = A[i] + S[i - 1];
        while(A[i] < s.top().ff){
            R[s.top().ss] = i;
            s.pop();
        }
        L[i] = s.top().ss;
        s.push({A[i], i});
    }
    plant(n);
    cout << solve(1, n, m.ss);
    return 0;
}

如果把範測的笛卡爾樹具象化，大概長這樣：

8
3 9 4 5 1 6 2 8

大致步驟就是：

  1. 用單調隊列建立函數 $L$ 以及 $R$，表示往左往右看第一個小於自己的數
  2. 建立笛卡爾樹（$L[i],R[i]$ 挑大的作為父節點）
  3. 從根節點開始走訪，左右節點就會分別是左右區間的最小值
  4. 利用前綴和計算區間大小，決定要走左還是右子樹
  5. 走訪到區間長度為 $1$ 時即答案！

總共有三個不同的作法，使用到排序、線段樹、笛卡兒樹的作法。其中，他們的間複雜度分別是 $O(n\log n)$、$O(n\log n)$、$O(n)$。

  1. 排序作法：AC (0.1s, 9.5MB)
  2. 線段樹作法：AC (84ms, 20.9MB)
  3. 歐恩作法：AC (82ms, 15.6MB)

在笛卡兒樹的作法中，對每一個數字尋找兩側第一個小於它的數字（這可以用單調隊列完成），之後把每一個數字的父親節點設為找到的兩端數字中較大的那一個。

此作法的概念是，假設序列中第 $i$ 個數字找到兩側數字分別是 $l_i$ 以及 $r_i$，當他如果是區間最小時，區間必須在 $[l_i+1:r_i-1]$ 之中，否則它就不會是最小值了。

至於為何是選擇 $max(A[l_i],A[r_i])$ 當做父節點？則是因為如果選擇較小的那一個，在縮小區間範圍後，無法確定另外一個是否在區間外，如果包含區間內，則 $A[i]$ 便不會是最小值，違反了定義。換言之，選擇了較大的那一個當作父節點，按照定義當走到這個父節點時，它是區間的最小值，將它排除之後，$A[i]$ 就會是下一個區間的最小值！