#33229: 解題思路


harlivy_forever (噴火水雞肉飯)

學校 : 國立嘉義高級中學
編號 : 160563
來源 : [140.113.136.220]
最後登入時間 :
2024-11-19 20:59:13
d900. NOIP2010 2.接水问题 -- NOIP2010普及组第二题 | From: [218.164.226.59] | 發表日期 : 2022-12-14 00:27

開一個大小為m的vector代表m個水龍頭,分別放m個水龍頭裝水花的總時間,重複挑出裡面最小值加上下一個裝水的人花的時間。以範例一為例:

原本的vector:4 4 1

排序:1 4 4 (1最小,代表這個位置的水龍頭最快空出來)

加上下個人:3(1+2) 4 4 

排序:3 4 4 

加上下個人:4(3+1) 4 4 

所有人都裝完水,從vector中挑出最大者(最慢裝完水):4

 

 

 
#34042: Re: 解題思路


wubaie (小億)

學校 : 不指定學校
編號 : 123253
來源 : [61.228.45.62]
最後登入時間 :
2024-11-23 14:59:02
d900. NOIP2010 2.接水问题 -- NOIP2010普及组第二题 | From: [111.240.59.94] | 發表日期 : 2023-02-25 16:46

開一個大小為m的vector代表m個水龍頭,分別放m個水龍頭裝水花的總時間,重複挑出裡面最小值加上下一個裝水的人花的時間。以範例一為例:

原本的vector:4 4 1

排序:1 4 4 (1最小,代表這個位置的水龍頭最快空出來)

加上下個人:3(1+2) 4 4 

排序:3 4 4 

加上下個人:4(3+1) 4 4 

所有人都裝完水,從vector中挑出最大者(最慢裝完水):4

 

 

C++ 優先佇列:
priority_queue<int,vector<int>, greater<int>> pq;

 
ZeroJudge Forum