# Greedy

是一個非常直觀的的演算法
每次都取最好的方法，前提是要先確保他會是對的，大多複雜度都不會太爛，$O(N)$，$O(NlogN)$
`Greedy`的題目大多都可以用`DP`來解，反過可能不行

## [a075]([https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a075])
就維護前綴和，再去遍歷每一個人就可以了

:::spoiler `虛擬碼`

child_right <- 1
sum <- 0
val() // get the ith students value
FOR child_left in (1 to child_amount) :
	WHILE child_right in child and  val( child_right+1 ) + sum < K : //K 耐久度 :
		sum <- val( child_right+1 ) + sum;
		child_right <- child_right + 1
	
	sum <- sum - val( child_left )
	

:::

## [a076](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a076)

對於每個右界去做排序，依序取，判斷可行的區間，更新範圍，輸出答案

:::spoiler `虛擬碼`

SORT( segments_right )
range <- (-inf, inf) //一開始的值域沒有範圍
ans <- 0
FOR segment in segments :
	IF segment in range :
		range <- [segment_right, inf)
		ans <- ans+1
	

:::

## [a078](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a078)

先對每一個作業依期限去做排序，對於每一個排序，放進完成的時間，如果完成的時間超過期限則每次取先前最大的完成時間

:::spoiler `虛擬碼`

SORT( homeworks.lim ) 
	
time_add() // 加入作業
time_cac() // 計算目前作業需要花的總時間 
time_cnt() // 計算有多少作業 
kick_max() // 把所花時間最多的作業踢出
FOR homework in homeworks :
	time_add(homework)
	WHILE time_cac() > homework.lim // IF 
		kick_max()
		
ans <- time_cac()

:::

## [a079](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a079)

一開始的每個人起始時間皆為0，然後每次去選取時間在最前面的人，依序放入即可

:::spoiler `虛擬碼`

worker.size = work_amount
worker_min(); //回傳最先可以服務顧客的那個員工，一開始都預設為0
worker_max(); //回傳所有員工中最後完成服務的那一個
FOR customer in Customers :
    worker_min() .time <- worker_min() .time + customer .time
   
ans <- worker_max();

:::

## [a080](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a080)
二分搜，判斷每一次的答案可不可以在時限內(透過`a079`的`greedy`)

:::spoiler `虛擬碼`

Function get_time( worker_amount ) :
    worker.size = worker_amount;
    worker_min(); //回傳最先可以服務顧客的那個員工，一開始都預設為0
    worker_max(); //回傳所有員工中最後完成服務的那一個
    FOR customer in Customers :
        worker_min() .time <- worker_min() .time + customer .time

    ans <- worker_max();
End Function

ans = use binary search find the max worker_amount let get_time( worker_amount )  lower that the limit

:::