貪心-學習了解記錄

本篇是在學習了解貪心的過程中留下的了解和記錄，主要是通過幾個題目來了解貪心的思路

這裡寫目錄标題

• • • 想法思路
    • • 題目一：一共有n個人，人的體重是w[i],船的上線重量是C，每條船最多是兩個人，問最少幾條船能把所有人裝走
      • 總結：
      • 題目二：區間問題，一條數軸上面有n個開區間(a(i),b(i)),選擇盡可能多的點使得區間之間沒有公共點
      • 總結：
      • 題目三：區間選點問題：一條數軸，n個閉區間[a(i),b(i)],取盡量少的點使得每一個區間都至少包含一個點
      • 總結：
      • 題目四：交代任務，有n個部下，每個部下有一個任務，交代任務的時間為B[i]執行任務的時間為j[i],不能同時對兩個部下交代任務，但是兩個任務可以同時執行，選擇交代順序使得所有的任務盡快完成
      • 題目五：酒交易，一條直線上有n（2<=n<=100000）個等距村莊，要麼買酒要麼賣酒，第i個村莊需求為ai，ai<0需要買酒，ai>0需要出售酒，所有ai相加等于0，k個機關的酒從一個村莊到相鄰的村莊要求是k的勞動力，最少要求多少勞動力

想法思路

1. 隻顧眼前，但是卻能得到最優解，讓眼前的浪費是最小的
2. 不能保證是唯一的最優解但是一定是最優解之一
3. 直覺地表示就是隻考慮局部，每次都拿最合适的一個，最後得到的就一定是最優解，但是如果出現多種限制條件的話就需要綜合考慮

題目一：一共有n個人，人的體重是w[i],船的上線重量是C，每條船最多是兩個人，問最少幾條船能把所有人裝走

1. 我們先将w(i)從小到大排序走一遍，當1是最輕的時候，他加2的重量還是比c大，那麼說明至少有n條船，因為兩個最輕的人都不能同船，那其他人就跟不可能在一起坐船了
2. 然後我們的思路走到第i和第k個人同船，如果存在j比k重，但是j和i又同船不超載，那麼我們就應該讓i和j一起坐船，這就是目前局部的最優解
3. 是以我們來回憶一下這題的解法，利用雙指針，i從最輕的開始走，j從最重的往回走，j先走，當j和最輕的都做不了船的時候，就說明此時的j需要一個人坐船，j一直遞減到第一個能和i坐船的情況，才會出現i+1的同時，j-1并且隻多一條船的情況，之後就繼續往下走就完事。

後續
           

總結：

這裡的貪心思路就是從最輕的開始找，每次找都是找能同船的最大的重量，到最後結果的時候就會轉化成最少需要幾條船

題目二：區間問題，一條數軸上面有n個開區間(a(i),b(i)),選擇盡可能多的點使得區間之間沒有公共點

1. 最多區間問題我們會考慮的多一點的就是，區間越小，有公共點的幾率就越低，是以我們需要先按照b(i)的大小來遞增排序，現在假設區間已經按照b(i)的大小排序好了(選左邊界或者右邊界都可以，具體就是判斷當一個邊界排序之後，另一個邊界的相交問題)，那麼下面我們來考慮左邊界的問題

• a1>a2

  如下圖所示，區域1被包含在區域2中，那按照貪心的政策直接拿最小的也就是b1

  

• 兩個區域不存在交集也就是a2>b1

  這就不影響判斷，直接把區域一拿進去就行

  

• a1<a2

  就是兩個區域相交的情況，那就是二選一呗，因為不能有公共點，但是我們其實仔細一看，前面斜線的部分其實是不影響選擇的，，已經在最前面了，選不選都不會影響到區間的個數(因為前面不可能有區間和他相交了)，但是我們選區域二就會包含區域一，而且後面的部分還有可能和其他部分相交，是以我們還是得選區域一。

  

1. 我們拿到第一個區間之後，排除所有和區域一相交的區域，從下一個和區域一不相交的區域開始，重複剛才的操作繼續确定下一個區域，最後掃描整個數軸就能完成貪心，得到最終的結果

後續
           

總結：

這裡的貪心思路就是在每個不相交的區間内選一個最大的區間，當每次選擇不相交最小的區間的時候就會得到最多的區間個數

題目三：區間選點問題：一條數軸，n個閉區間[a(i),b(i)],取盡量少的點使得每一個區間都至少包含一個點

1. 假如區間i有點，那麼所有包括區間i的區間都被滿足。
2. 還是先對所有的區間按照b(i)大小進行增序，當b(i)相同的時候，a(i)進行遞減排序(這樣如果碰到相同的我們直接計b(i)相同a(i)最大的一次就好了)

   

3. 接下來每次去找的時候就去找最小的區間，然後每次取點就是最小區間的最右點，把所有的有交集的區間都去除掉之後再去尋找下一個最小的區間，重複目前過程

總結：

這裡的貪心思路就是擷取每一個最小的區間來獲得點，每次獲得最小區間之後把右邊所有相交的區間都删除，這樣重複的操作

後續
           

題目四：交代任務，有n個部下，每個部下有一個任務，交代任務的時間為B[i]執行任務的時間為j[i],不能同時對兩個部下交代任務，但是兩個任務可以同時執行，選擇交代順序使得所有的任務盡快完成

按照直覺來說，執行時間越長的越應該放在前面，當然隻靠直接還是不準的，下面舉個簡單的栗子來證明一下

• 交代事件相同的情況下

  如下可以看出執行時間長的在前面是比較優秀的回答

  

• 交代事件不相同的情況下

  如下可以看出執行時間長的在前面是比較優秀的回答

  

後續
           

題目五：酒交易，一條直線上有n（2<=n<=100000）個等距村莊，要麼買酒要麼賣酒，第i個村莊需求為ai，ai<0需要買酒，ai>0需要出售酒，所有ai相加等于0，k個機關的酒從一個村莊到相鄰的村莊要求是k的勞動力，最少要求多少勞動力

1. 從最左便開始考慮，如果a1大于0，說明肯定有酒從2号村莊到一号村莊去，勞動力就是k，那麼我們現在假設有四個村莊，不難看出其實最後的勞動力就等于每個相鄰的村莊相加最後得出的結果

   

後續