ap325第四章

二月 15, 2025

AP325

貪心演算法(Greedy algorithm)

特性:

算法由一連串決定組成(由大到小逐一考慮各種代幣的數量)，每次考慮當前最好
決定(能換盡量換)，選擇後就不再更改。
算法的正確性必須經過證明，內容就是要證明所下的決定是對的，也就是一定有一
個最佳解包含了貪心法所做的決定，而證明的方法通常都是用換的：假設有一個最
佳解跟貪心法做的決定不一樣，那麼，我們可以換成一個與貪心法一樣的決定，而
解會更好，或至少不會變差。
note:個人覺得貪心是必須在數學規律上下功夫，找到題目的特性，所以貪心是程式簡單，但想出規律卻是難的

優先佇列(priority_queue)

top會是最大值
如果要讓top為最小值可以加上負號讓大小關係反轉
priority_queue<pair<int,int>> pq; 會先比對pair的first
加入新元素(push)，O(log(n))
查詢最大值(top)，O(1)
刪除最大值(pop)，O(log(n))
檢查是否為空(empty)，O(1)
比set快兩倍以上!!!

例題 P-4-2. 笑傲江湖之三戰

https://judge.tcirc.tw/problem/d043
都是用貪心算法，找到最優解法
自己寫:

#include <bits/stdc++.h>

using namespace std;
bool cmp(int a,int b){
    return a<b;
}
int main()
{
    int n;
    cin>>n;
    int temp;
    int ans=0;
    deque<int>pq1;
    deque<int>pq2;

    for(int i=0;i<n;i++){
        cin>>temp;
        pq2.push_back(temp);
    }
    for(int i=0;i<n;i++){
        cin>>temp;
        pq1.push_back(temp);
    }
    sort(pq1.begin(),pq1.end(),cmp);
    sort(pq2.begin(),pq2.end(),cmp);
    /*for(auto t:pq1){
        cout<<t<<' ';
    }
    cout<<'\n';
    for(auto t:pq2){
        cout<<t<<' ';
    }
    cout<<'\n';*/
    while(!pq1.empty()){
        if(pq1.front()>pq2.front()){
            pq1.pop_front();
            pq2.pop_front();
            ans++;
        }else{
            pq1.pop_front();
            pq2.pop_back();
        }
    }
    cout<<ans;
    return 0;
}

例題 P-4-3. 十年磨一劍 (最少完成時間)

https://judge.tcirc.tw/problem/d044

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main()
{
    LL n;
    cin>>n;
    priority_queue<LL,vector<LL>,greater<LL>> pq;
    LL temp;
    for(LL i=0;i<n;i++){
        cin>>temp;
        pq.push(temp);
    }
    LL ans=0;
    temp=0;
    for(LL i=0;i<n;i++){
        temp+=pq.top();
        pq.pop();
        ans+=temp;
    }
    cout<<ans;
    return 0;
}

P-4-4. 幾場華山論劍(activity selection)

https://judge.tcirc.tw/problem/d045
「若[x,y]是所有現存線段中右端點最小的，那麼一定有個最佳解是挑選了[x,y]。」
證明：假設最佳解沒有挑[x,y]，令[a,b]是最佳解中右端點最小的。根據我們的假設，
y <= b，因此將[x,y]取代[a,b]不會重疊到任何最佳解中的其他線段，我們可以得到
另外一個最佳解包含[x,y]。
根據此性質，我們可以不斷地將最小右端的線段挑選進解答，然後略過任何與它重疊的
線段。因為線段不會改變，一開始依照右端由小排到大，然後從頭到尾掃描一次就可以
得到答案。
自己寫:

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
struct act{
    int l;
    int r;

};
bool cmp(act a,act b){
    return a.r<b.r;
}
int main()
{
    int n;
    LL temp1,temp2;
    act s[100010];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i].l>>s[i].r;
    }
    sort(s,s+n,cmp);
    LL ans=1;
    temp1=s[0].r;
    for(int i=1;i<n;i++){
        if(temp1<s[i].l){
            temp1=s[i].r;
            ans++;
        }

    }
    cout<<ans;

    return 0;
}

P-4-5. 嵩山磨劍坊的問題(加權最小完成時間)

https://judge.tcirc.tw/problem/d046
有權重的問題都要繞彎……
重點是數學上加權的比較，觀察發現t/w的數值越小應該要排在越前面
證明:

經過推導:變化量=W[i]t[i+1]-w[i+1]*t[i]
假設t[i]/w[i] > t[i+1]/w[i+1] 交叉相乘得到
w[i+1]*t[i]<t[i+1]*w[i] 運算
w[i]*t[i+1]-w[i+1]*t[i]<0 也就是變化量為負，交換解會更好
自己寫:

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;

bool cmp(pair<int,int>a,pair<int,int>b){
    return a.first*b.second<b.first*a.second;
}

int main(){
    int n;
    cin>>n;
    LL temp;
    deque<pair<int,int>>dq;
    for(int i=0;i<n;i++){
        cin>>temp;
        dq.push_back({temp,0});
    }
    for(int i=0;i<n;i++){
        cin>>temp;
        dq[i]={dq[i].first,temp};
    }
    sort(dq.begin(),dq.end(),cmp);
    LL total=0;
    temp=0;
    for(auto t:dq){
        //cout<<t.first<<' '<<t.second<<'\n';
        temp+=t.first;
        total+=temp*t.second;
    }
    cout<<total;
    return 0;
}

Q-4-6. 少林寺的自動寄物櫃 (APCS201710)

習題
發現要自己推導出數學規律是十分困難且耗時的，而且很需要數感的天分，以後寫到背包問題後再重新寫一次看看。
自己寫:

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;

bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first*b.second<b.first*a.second;
}

int main(){
    int n;
    cin>>n;
    LL temp;
    deque<pair<int,int>> dq;
    for(int i=0;i<n;i++){
      cin>>temp;
      dq.push_back({temp,0});
    }
    for(int i=0;i<n;i++){
      cin>>temp;
      dq[i]={dq[i].first,temp};
    }
    sort(dq.begin(),dq.end(),cmp);
    temp=0;
    LL ans=0;
    bool valid=true;
    for(auto t:dq){
        //cout<<t.first<<' '<<t.second<<'\n';
        if(valid){
            valid=false;
            temp+=t.first;
            continue;
        }
        ans+=temp*t.second;
        temp+=t.first;
    }
    cout<<ans;
    return 0;
}

P-4-7. 岳不群的併派問題 (Two-way merge) (*)

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    long long  temp;
    priority_queue<long long ,vector<long long>,greater<long long>> pq;
    long long sum=0;
    for(int i=0;i<n;i++){
        cin>>temp;
        sum+=temp;
        pq.push(temp);
    }
    long long ans=0;
    long long t;
    while(!pq.empty()){
        temp=pq.top();
        pq.pop();
        t=(pq.top()+temp);
        pq.pop();
        pq.push(t);
        ans+=t;
        //cout<<ans;
        if(pq.size()<=1) break;
    }
    cout<<sum<<'\n'<<ans;
    return 0;
}

note. priority q設定的是greater與less

Q-4-8. 先到先服務 (*)

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main()
{
    LL n,m;
    cin>>n>>m;
    priority_queue<LL,vector<LL>,greater<LL>> pq;
    LL temp;
    LL x;
    for(LL i=0;i<n;i++){
        cin>>x;
        if(((LL)pq.size())>=m){
            temp=pq.top();
            pq.pop();
            x+=temp;
            //cout<<x<<' ';
            pq.push(x);
        }else{
            //cout<<x<<' ';
            pq.push(x);
        }
    }
    while(pq.size()>1){
        pq.pop();
    }
    cout<<pq.top();


    return 0;
}

貪心演算法經常可以搭配二分搜

P-4-9. 基地台 (APCS201703)

講義裡的答案
服務點可以看成數線上的點，基地台可以看成數線上的線段，要計算以K根長度相同的
線段蓋住所有的點，最小的線段長度。這一題是給數量K要求長度R。要解決這個問題，
先看以下問題：輸入給數線上N個點以及R，請問最少要用幾根長度R的線段才能蓋住
所有輸入點。
note.他要的就是最短的線段，所以她的做法是找出最短的線段還要短的那個，找出來後+1就是答案了。

#include <bits/stdc++.h>

using namespace std;
int p[600000],n,k;
bool enough(int r){
    int nseg=k,endline=-1;
    for(int i=0;i<n;i++){
        if(p[i]<=endline) continue;
        if(nseg==0) return false;
        nseg--;
        endline=p[i]+r;
    }
    return true;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    sort(p,p+n);
    int len=0,L=p[n-1]-p[0];
    for(int jump=L/2;jump>0;jump/=2){
        while(len+jump<L&&!enough(len+jump)){
            len+=jump;
        }
    }
    cout<<len+1;
    return 0;
}

Q-4-10. 恢復能量的白雲熊膽丸

https://judge.tcirc.tw/problem/d054
雖然是一樣的練習題，不過自己寫出來成就感很大，一樣是找比最小的體力值更小的那個，二分搜尋法真是神奇

#include <bits/stdc++.h>
//8 2 3 4 1 7 4 12 10 1
using namespace std;
int p[5000000],n,m;
bool enough(int F){
    int time=m;
    int body=F;
    for(int i=0;i<n;i++){
        if(body-p[i]>=0){
            body-=p[i];
            continue;
        }
        body=F;
        if(body<p[i]) return false;
        body-=p[i];
        time--;
        if(time<0) return false;
    }
    return true;
}
int main()
{

    cin>>n>>m;
    int maxx=0;
    for(int i=0;i<n;i++){
        cin>>p[i];
        maxx+=p[i];
    }
    int F=0;
    for(int jump=maxx;jump>0;jump/=2){
        //cout<<F<<' '<<jump<<'\n';
        while(!enough(F+jump)){
            F+=jump;
        }
    }
    cout<<F+1;
    return 0;
}

P-4-11. 線段聯集 (APCS 201603)

https://judge.tcirc.tw/problem/d050
以下解法為tle解，因為下率實在是太差了

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
LL s[100000050]={};
int main()
{
    LL n;
    LL a,b;
    cin>>n;
    LL minn=1000000,maxx=-1;
    for(LL i=0;i<n;i++){
        cin>>a>>b;
        minn=min(a,minn);
        maxx=max(b,maxx);
        for(LL j=a;j<b;j++){
            s[j]++;
        }
    }

    LL sum=0;
    for(LL i=minn;i<=maxx;i++){
        //cout<<s[i]<<' ';
        if(s[i]>=1){
            sum+=1;
        }
    }
    cout<<sum;
    return 0;
}

用以下方法掃描:
時間複雜度為O(n*logn)就可以通過題目了

#include <bits/stdc++.h>

using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
int main()
{
    int n;
    cin>>n;
    int a,b;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        pq.push({a,b});
    }
    pair<int,int>last=pq.top();
    pq.pop();
    int sum=0;
    while(!pq.empty()){
        while(last.second>pq.top().first){
            if(last.second<pq.top().second)last.second=pq.top().second;
            pq.pop();
            if(pq.empty()){
                break;
            }
        }
        sum+=(last.first-last.second);
        if(pq.empty()){
            cout<<-sum;
            return 0;
        }
        last=pq.top();
        pq.pop();
    }
    sum+=(last.first-last.second);
    cout<<-sum;
    return 0;
}

P-4-12. 一次買賣

https://judge.tcirc.tw/problem/d051
想像成一條掃描線

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    long long s[n];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    long long minn=s[0];
    long long maxx=-1;
    for(int i=1;i<n;i++){
        maxx=max(maxx,s[i]-minn);
        minn=min(minn,s[i]);
    }
    cout<<maxx;
    return 0;
}

P-4-13. 最大連續子陣列 (同 P-5-2)

https://judge.tcirc.tw/problem/d052
P-4-13與P-4-12有何關係呢？P-4-12的輸入是每日價格，如果把每日價格與前一
日的價差放在A[]中，A[i]=p(i)-p(i-1)，那麼就變成P-4-13了，因為連續一段
時間的累積價差就等於最後一日與最前一日的價差
A[i]+A[i+1]+…A[j]=(p(i)-p(i-1))+(p(i+1)-p(i))+…+(p(j)-p(j-1))
=p(j)-p(i-1)
note.我覺得有點數學理論了，一般很難想的到
這裡的想法是原先給的陣列是一個差值陣列(A)，然後把他轉成真正的數值陣列(P)，那數值陣列中的max-min就會是差值陣列的解

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main()
{
    LL temp;
    int n;
    cin>>n;
    LL s[100010]={};
    s[0]=0;
    for(int i=1;i<=n;i++){
        cin>>temp;
        s[i]=s[i-1]+temp;
    }
    LL minn=s[0];
    LL maxx=-1;
    //cout<<s[0]<<' ';
    for(int i=1;i<=n;i++){
        maxx=max(maxx,s[i]-minn);
        //cout<<s[i]<<' ';
        minn=min(minn,s[i]);

    }
    //cout<<'\n';
    if(maxx>0)cout<<maxx;
    else cout<<0;
    return 0;
}

而為了更直觀，講義裡提到了:Kadane's Algorithm

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int main()
{
    LL n,max_sum=0;
    LL p_max=0;
    cin>>n;
    for(int i=0;i<n;i++){
        LL p;
        cin>>p;
        p_max=(p_max>0)? p_max+p:p;
        max_sum=max(max_sum,p_max);
    }
    cout<<max_sum;
    return 0;
}

程式邏輯（Kadane’s Algorithm）
這個程式實現了 Kadane 演算法，用於解決最大子數組和問題。
核心思想是：
遍歷數組，對於每個元素，決定是將其加入前面的子數組，還是從該元素開始新子數組。
維護兩個變數：

p_max：以當前元素結尾的子數組的最大和。
max_sum：全局的最大子數組和。
如果 p_max 為負數，則捨棄之前的子數組，從當前元素重新開始，因為負數只會減小後續的和。

P-4-14. 控制點 (2D-max)

https://judge.tcirc.tw/problem/d055

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int main()
{
    int n;
    cin>>n;
    pair<LL,LL> s[100010];
    for(int i=0;i<n;i++){
        cin>>s[i].first;
    }
    for(int i=0;i<n;i++){
        cin>>s[i].second;
    }
    sort(s,s+n); //x increasing
    /*for(int i=0;i<n;i++){
        cout<<s[i].first<<' '<<s[i].second<<'\n';
    }*/
    //cout<<'\n';
    int ans=1;
    LL max_y=s[n-1].second;
    for(int i=n-2;i>=0;i--){
        //cout<<ans<<' '<<max_y<<'\n';
        if(s[i].second>max_y){
            ans++;
        }
        max_y=max(max_y,s[i].second);

    }
    cout<<ans;
    return 0;
}

P-4-15. 最靠近的一對(closest pair) (@@)

https://judge.tcirc.tw/problem/d056
tle解，正解以後再學

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int main()
{
    int n;
    cin>>n;
    pair<LL,LL> s[100010];
    for(int i=0;i<n;i++){
        cin>>s[i].first>>s[i].second;
    }
    sort(s,s+n);
    LL minn=1000000000;
    deque<LL> q;
    q.push_front(0);
    for(int i=1;i<n;i++){
        if(abs(s[i].first-s[q.front()].first)+abs(s[i].second-s[q.front()].second)>minn){
            q.pop_front();
        }

        for(auto t:q){
            minn=min(minn,abs(s[i].first-s[t].first)+abs(s[i].second-s[t].second));
        }
        q.push_back(i);
    }
    cout<<minn;
    return 0;
}

查看评论