j608. 4. 機器出租

2023.1.18 PM 05:30 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=j608
出題者 : 2023年1月APCS
標籤 : 貪心法、二分搜尋法
難易度 : 4

解題想法 : 
此題的40%解是個很經典的貪心法排程問題[圖像化筆記連結]，而剩餘的60%也同樣是貪心原則，並需搭配二分搜尋法來優化常數。

40%解 - 依結尾時間排序 (見C++ Code - 40%)
首先將每個時段的{開始時間, 結束時間}綁成一個pair，並以結束時間由小到大排序，如果結束時間相同，那就以開始時間較大(時段較短)的優先。
再來遍歷排好序的時段，只要符合的就拿(開始時間嚴格大於先前的結束時間)，遍歷完以後，拿的次數就是答案。

AC解 - 排序後，分配時段給空閒的機器
排序後，我們會需要一個大小為k的陣列，裡頭存放每個機器最後一個工作的結束時間(編號不重要)，為了方便，每台機器初始的結束時間皆為-1。
再來一樣遍歷排好序的時段，只要有任何一台機器工作的結束時間嚴格小於當前的開始時間，就把答案+1，並把機器的結束時間更新成當前的結束時間，倘若有多個符合的選項，依據貪心法很重要的慣老闆理論，以最接近當前開始時間的為優先。

此處可以發現，假如我們維護好結束時間的陣列，使它由小到大排序，是不是就具有二分搜尋的性質?
C++可以使用multiset來達成這件事，而二分搜尋也可以使用內建的lower_bound。

Python則需使用insort()維護插入後的排序狀態，且排序需使用cmp_to_key()，來達成多個元素的比較。

//C++ language - 40%

#include<iostream>
#include<utility> //pair
#include<vector> //vector 
#include<algorithm> //sort()
using namespace std;
bool cmp(pair<int,int>a, pair<int,int>b){
    if(a.second==b.second) return a.first>b.first;
    return a.second<b.second;
}
int main(){
    int n,k; cin>>n>>k;
    vector<pair<int,int>>v(n);
    for(int i=0;i<n;i++) cin>>v[i].first;
    for(int i=0;i<n;i++) cin>>v[i].second;
    sort(v.begin(),v.end(),cmp);
    
    int ans=1;
    pair<int,int> last=v[0];
    for(int i=1;i<v.size();i++){
        if(v[i].first>=last.second+1){
            ans++;
            last=v[i];
        }
    }
    
    cout<<ans<<'\n';
    
    return 0;   
}

//C++ language - AC

#include<iostream>
#include<utility> //pair
#include<vector> //vector 
#include<algorithm> //sort(), lower_bound()
#include<set> //multiset
#define st_it set<int>::iterator
using namespace std;
bool cmp(pair<int,int>a, pair<int,int>b){
    if(a.second==b.second) return a.first>b.first;
    return a.second<b.second;
}
int main(){
    int n,k; cin>>n>>k;
    vector<pair<int,int>>v(n);
    for(int i=0;i<n;i++) cin>>v[i].first;
    for(int i=0;i<n;i++) cin>>v[i].second;
    sort(v.begin(),v.end(),cmp);
    
    multiset<int>st;
    for(int i=0;i<k;i++) st.insert(-1);
    
    int ans=0;
    for(pair<int,int>p: v){
        int start=p.first, end=p.second;
        st_it era = st.lower_bound(start);
        if(era==st.begin()) continue;
        era--;
        st.erase(era);
        st.insert(end);
        ans++;
        
    }
    
    cout<<ans<<'\n';
    
    return 0;   
}

## Python language

from functools import cmp_to_key
from bisect import bisect_left,insort
def comp(a,b):
    if a[1]==b[1]: return b[0]-a[0]
    return a[1]-b[1]
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
v=[x for x in zip(a,b)]
v.sort(key=cmp_to_key(comp))
end_time=[-1]*k
ans=0
for start,end in v:
    lb = bisect_left(end_time,start)
    if lb==0: continue
    end_time.pop(lb-1)
    insort(end_time,end)
    ans+=1 
print(ans)

相關文章

分享此文：