g597. 3. 生產線

2023.1.24 PM 09:30 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=g597
出題者 : 2021年11月APCS
標籤 : 差分法、貪心法
難易度 : 3

解題想法 : 
使用貪心的想法，我們會希望要產出最多量的時間點可以是效率最高的那台來做，而做最少次的就安排給它效率最差的那台，那要如何取得每個時間點需要產出的量呢？一個有效率的方法是使用差分法，詳細可參考[圖像化筆記連結]。

有了每個時間點要產出的量後，就能夠安排給每台機器，由於時間點和機器們的順序性沒有任何意義，所以可以對兩者進行排序(一個順序一個反序)，然後再將每組(時間點[i],機器[i])的乘積加總就是最佳的解。

// C++ language

#include<iostream>
#include<tuple> //tuple, tie
#include<vector> //vector 
#include<algorithm> //sort()
using namespace std;
int main(){
    int N,M; cin>>N>>M;
    tuple<int,int,int> task[M];
    
    for(int i=0;i<M;i++){
        int a,b,c; cin>>a>>b>>c;
        task[i] = tie(a,b,c);
    }
    vector<int> sec(N);
    for(int &i: sec) cin>>i;
    
    int diff[N+2]={0},L,R,W;
    for(tuple<int,int,int> T: task){
        tie(L,R,W)=T;
        diff[L]+=W; diff[R+1]-=W;
    }
    
    int tot=0;
    vector<int> tot_load;
    for(int i:diff) tot+=i, tot_load.push_back(tot);
    
    sort(tot_load.begin(),tot_load.end(),greater<int>());
    sort(sec.begin(),sec.end());
    
    long long ans=0;
    for(int i=0;i<N;i++) ans+=tot_load[i]*sec[i];
    cout<<ans<<"\n";
    return 0;
}

## Python language

N,M = map(int,input().split())
task=[]
for i in range(M): task.append([int(x) for x in input().split()])
sec=[int(x) for x in input().split()]

diff=[0]*(N+2)
for L,R,W in task:
    diff[L]+=W
    diff[R+1]-=W

tot=0
tot_load=[]
for i in diff[1:-1]:
    tot+=i
    tot_load.append(tot)
    
tot_load.sort(reverse=True)
sec.sort()

ans=0
for i in range(N): ans+=tot_load[i]*sec[i]

print(ans)

相關文章

分享此文：