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)
