Peienwu's Blog

Hello world

0%

[題解]APCS生產線

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

P3 生產線

題目連結

差分作法

題解

用差分的想法加值，再用前綴還原，最後再排序。最後利用Greedy的想法，將每一項最小的工作量乘上最大的時間，總和即為答案。

差分

差分是前綴和的逆運算，也就是說，把兩項的差算出來就是差分。定義如下：

差分的使用時機是區間加值，一個區間內的數字都加上一個定值，這時候就可以使用到差分的技巧。使用方式如下，當我要在區間 $[l,r]$ 的每一個數字都加上一個值$v$，以下步驟：

  1. 定義一個新的陣列 $b_i$ 表示每一項差分
  2. 設 $b[l] = b[l] + v,b[r+1] = b[r+1] - v$
  3. 將差分的每一項加上前一項（做前綴和 $b[i] = b[i]+b[i-1]$），即為原數列

第二步驟可以重複好幾次做，這樣複雜度從原本的$O(n)$就變成了$O(1)$了！

時間複雜度

差分：$O(m)$ 、排序 $O(n\log n)$

總時間複雜度：$O(n\log n + m)$

AC程式碼

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
#include <bits/stdc++.h>
#define int long long
#define N 200005
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,m,A[N],B[N];

signed main(){
    IOS;
    memset(A,0,sizeof(A));
    cin>>n>>m;
    while(m--){
        int x,y,w;cin>>x>>y>>w;
        A[x] += w;
        A[y+1] -= w;
    }
    for(int i=1;i<=n;i++)cin>>B[i];
    for(int i=1;i<=n;i++)A[i] = A[i] + A[i-1];
    sort(A+1,A+n+1);
    sort(B+1,B+n+1);
    int ans = 0;
    for(int i=1;i<=n;i++){
        ans += A[i] * B[n-i+1];
    }
    cout<<ans<<endl;
}

BY peienwu

線段樹作法

很奇怪，最近兩次的APCS第三題都有人想要砸資結，特別是線段樹，可能有些人特別偏愛線段樹吧！

題解

線段樹最原本的應該是區間詢問、單點修改，如果要區間修改的話就會用到懶標，所以實作上相對上比較複雜一點。這一題用線段樹的目的是區間加值，加值完過後的排序以及Greedy跟差分的作法是一樣的，用線段樹真的是多此兩舉（實作較複雜、較耗時）！

當然，這一題比較特別只有最後一起做單點查詢，因此不用懶標，最侯直接計算一路去經過的答案也行！下面的程式碼就是把完全包含區間的節點加值，不用使用到懶標，最後一次查詢。

時間複雜度

區間加值 $O(m\log n)$，n個點的詢問 $O(n\log n)$，排序 $O(n\log n)$

總時間複雜度：$O((n+m)\log n)$

AC程式碼

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
#include <bits/stdc++.h>
#define int long long
#define N 200005
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,m,t,A[N],B[N],ans = 0;

struct node{
    int val = 0,sz;
}seg[4*N];

void build(int id,int l,int r){
    seg[id].sz = r - l;
    if(r - l <= 1)return;
    int mid = (l + r) / 2;
    build(id*2,l,mid);
    build(id*2+1,mid,r);
}
void modify(int id,int l,int r,int ql,int qr,int val){
    if(r <= l || r <= ql || l >= qr)return;
    if(ql <= l && qr >= r){
        seg[id].val += val;
        return;
    }
    int mid = (l + r) / 2;
    modify(id*2,l,mid,ql,qr,val);
    modify(id*2+1,mid,r,ql,qr,val);
}
void query(int id,int l,int r,int val){
    if(r <= l)return;
    ans += seg[id].val;
    if(r - l == 1)return;
    int mid = (l + r) / 2;
    if(val < mid)return query(id*2,l,mid,val);
    else return query(id*2+1,mid,r,val);
}

signed main(){
    IOS;
    cin>>n>>m;
    build(1,1,n+1);
    while(m--){
        int x,y,w;cin>>x>>y>>w;
        y++;
        modify(1,1,n+1,x,y,w);
    }
    for(int i=1;i<=n;i++){
        ans = 0;query(1,1,n+1,i);
        A[i] = ans;
    }
    for(int i=1;i<=n;i++)cin>>B[i];
    
    sort(A+1,A + n + 1);
    sort(B+1,B + n + 1);
    int ans = 0;
    for(int i=1;i<=n;i++)ans += A[i] * B[n-i+1];
    cout<<ans<<endl;
}