貪心算法小結2

F-Ants

一隊螞蟻在一根水平桿上行走，每只螞蟻固定速度 1cm/s. 當一只螞蟻走到桿的盡頭時，立即從稈上掉落. 當兩只螞蟻相遇時它們會掉頭向相反的方向前進. 我們知道每只螞蟻在桿上的初始位置, 但是, 我們不知道螞蟻向哪個方向前行. 你的任務是計算所有螞蟻都桿上掉落可能的最短時間和最長時間.

Input

第一行包含一個整數，給出測試實例數量. 每組數據開始有兩個整數: 桿的長度 (單位：cm) 和桿上螞蟻數量 n. 之后是 n 個整數給出每只螞蟻從桿的最左邊開始的位置, 且是無序的. 輸入的每個整數都不大于 1000000 ，兩個數字用空格分開.

Output

對于每組輸入輸出兩個整數. 第一個整數表示所有螞蟻從桿上掉落可能的最短時間（如果它們前行方向選擇得當） ，第二個整數表示可能的最長時間.

Sample Input

2
10 3
2 6 7
214 7
11 12 7 13 176 23 191

Sample Output

4 8
38 207
　　解題思路：這個題想明白一點就好寫了。即螞蟻的速度是一樣的，轉身不消耗時間，那么可以將兩只相遇時掉頭的螞蟻，看做交錯而過，不理會相遇即可。因為掉頭與交錯而過的時間是一樣的。再暴力搜素每一個螞蟻的位置，如果是最短時間，則比較
它距桿左邊的距離與距桿右邊的距離取最小，取出最大的最小值，即為所求 。如果是最長時間，比較它與桿左邊的距離與桿右邊的距離取最大，最后取出最大值。代碼如下：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <map>
#include <stack>
#include <utility>
using namespace std;
int const max_n=500;
int a[max_n];
int main()
{int m,n,t;scanf("%d",&t);while(t--){cin>>m>>n;for(int i=0;i<n;i++)cin>>a[i];int minN=0,maxN=0;//最短時間，最長時間for(int i=0;i<n;i++)minN=max(minN,min(a[i],m-a[i]));for(int i=0;i<n;i++)maxN=max(maxN,max(a[i],m-a[i]));cout<<minN<<" "<<maxN<<endl;memset(a,0,sizeof(a));}return 0;
}

?G-Fence Repair

Description

It is universally accknowledged that 泥煤(peat)是一個非常珍貴的收藏品，越大的泥煤收藏價值越高。

一天，王泥煤找到了阿拉伯神燈，也就是阿拉丁神燈的弟弟，他向阿拉伯神燈許了一個愿望，從此獲得了一個超能力，可以將兩個泥煤合并為更大的泥煤。但是這個能力非常的雞肋，王泥煤需要支付與這兩塊泥煤等價值的財富才能將他們合并。

比如：王泥煤把兩塊價值分別為3和5的泥煤合并，可以得到一塊價值為8的泥煤，但是要消耗3+5的財富。

王泥煤想知道，他將手中的n塊泥煤合并到只剩下一塊之后，最少需要花費多少財富。

Input

第一行為一個整數n（n <= 20000），代表王泥煤擁有的泥煤數量，接下來n行，每行一個整數a_i(1 <= a_i <= 50000)，代表每個泥煤的價值

Output

輸出包括一行，請告訴王泥煤他需要花費的最少財富。

Sample Input

3
8
5
8

Sample Output

34

?　　解題思路：就是不斷選取最小的兩塊煤進行合成，合成后放入煤堆再找兩個最小的，如果取一次排序一次，時間復雜度太高o（n^2），因此要用到優先隊列 ，注意使用默認的greater 按升序排序就可以了。注意數據范圍，要開long long 代碼如下：

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define LL long long
using namespace std;
int main()
{int n,x;LL maxq=0;scanf("%d",&n);priority_queue<LL,vector<LL>,greater<LL> >q;for(int i=0;i<n;i++){scanf("%d",&x);q.push(x);}while(q.size()!=1){LL a,b;a=q.top();q.pop();b=q.top();q.pop();LL c=a+b;q.push(c);maxq+=c;}cout<<maxq<<endl;return 0;
}

?H-最少攔截系統

某國為了防御敵國的導彈襲擊,發展出一種導彈攔截系統.但是這種導彈攔截系統有一個缺陷:雖然它的第一發炮彈能夠到達任意的高度,但是以后每一發炮彈都不能超過前一發的高度.某天,雷達捕捉到敵國的導彈來襲.由于該系統還在試用階段,所以只有一套系統,因此有可能不能攔截所有的導彈.?
怎么辦呢?多搞幾套系統唄!你說說倒蠻容易,成本呢?成本是個大問題啊.所以俺就到這里來求救了,請幫助計算一下最少需要多少套攔截系統.?

Input輸入若干組數據.每組數據包括:導彈總個數(正整數),導彈依此飛來的高度(雷達給出的高度數據是不大于30000的正整數,用空格分隔)?
Output對應每組數據輸出攔截所有導彈最少要配備多少套這種導彈攔截系統.?
Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

2
　　解題思路：因為不能漏掉任何一個導彈，所以要從第一個導彈開始，構建一個下降子序列；而在構建下降過程中的導彈若高于上一個導彈，則必須要使用新的攔截系統。這題我一開始寫的挺復雜的，過了之后看題解，發現自己想復雜了，可以開一個數組，輸入一個
導彈高度 ，若高于現在所有的攔截系統的高度，則必須新開一個攔截系統；若有攔截系統能夠攔下它，則更新該攔截系統的高度。參考鏈接：https://blog.csdn.net/sdut_jk17_zhangming/article/details/79292887
代碼如下：

#include<stdio.h>int main()
{int a[300] = {0},i,n,j,h,m;while(scanf("%d",&n) != EOF){m = 0;for(i= 0;i <n;i++){scanf("%d",&h);for(j = 0;j <m;j++){if(a[j] >= h)break;}if(j <m)a[j] = h;else{a[m] = h;m++;}}printf("%d\n",m);}return 0;
}

　　寫題的過程中，有不會的是很正常的，若是自己能寫過，就堅持寫完，寫完找找題解，了解別人的思路再與自己的思路對比，最好能學到最優解。所有做題過程中不要太過于糾結題解問題，關鍵在于看了有沒有學會最優解（或者說相對較好的思路）。

?

J - Packets

?

一家工廠生產的產品規格分為1×1, 2×2, 3×3, 4×4, 5×5, 6×6，高都是h。工廠要把它們包在6×6×h的包裝袋中。工廠想讓包裝數盡可能少。

Input

多組數據。每一行為一組數據。依次是1×1, 2×2, 3×3, 4×4, 5×5, 6×6的產品的個數。 輸入數據由6個0結束。

Output

對于每組數據，輸出包裝所有產品所需最少包裝袋數量

Sample Input

0 0 4 0 0 1 
7 5 1 0 0 0 
0 0 1 0 1 0
0 0 0 0 0 0 

Sample Output

2 
1
2 

?　　思路：這是一道二維裝箱題，而裝箱問題一般來說比較復雜，如果針對每一種情況進行精確算法是非常繁瑣且容易出錯的。在這里我用到了ceil()函數，返回大于或等于表達式值的函數來簡化算法。（參考鏈接http://blog.csdn.net/c20190413/article/details/77396357###）首先看，4×4,5×5,6×6的箱子，很顯然這三種箱子沒有一個就要占用一個包裝袋，6×6的箱子直接占用一個包裝袋，而5×5的箱子則可以塞進去11個1×1的箱子，用1×1箱子的個數減去min(a,e*11)（a為1×1箱子個數，e為5×5箱子個數，為表述方便，依次為箱子編號a、b、c、d、e、f）；對于一個4×4箱子，可以塞進2×2的箱子5個，若2×2箱子數不足時，可以補充1×1箱子;b-=min(b,d*5),若2×2箱子數不足時則有a-=min(a,4*(d*5-b))。

　　然后看3×3的箱子，分四種情況，箱子數為4的倍數，除以4余3、余2、余1,3種情況，這里選余2的情況為例子闡述。這時還有若干個1×1箱子若干個2×2箱子，兩個3×3箱子；分析易知，此時最多可以放入3個2×2箱子，最少放入6個1×1箱子才能把包裝袋填滿。首先判斷2×2箱子剩余數量有沒有3個，不足3個的部分，用1×1箱子補充，不足時有a-=min(a,(3-b)*4);然后進行a-=min(a,6);b-=min(b,3)。其余情況依此類推。使用min函數保證不出現負數。剩余的就是若干個1×1箱子和2×2箱子，使用ceil函數可以很快解決。代碼如下：

?

#include <iostream>
#include <algorithm>
#include <math.h>
#define LL long long
int const max_n=20;
using namespace std;
int main()
{int a,b,c,d,e,f;while(1){cin>>a>>b>>c>>d>>e>>f;if(!a&&!b&&!c&&!d&&!e&&!f)break;int num=0;num=d+e+f;a-=min(a,e*11);//減去應補充e箱子的a箱子if(b<d*5)a-=min(a,4*(d*5-b));//b箱子不足時，使用a箱子b-=min(b,d*5);//減去補充d箱子的b箱子num+=ceil(c/4.0);//向上取整c%=4;if(c==1){//多余1個3×3的箱子時if(b<5)a-=min(a,4*(5-b));//先判斷b箱子數量是否足夠a-=min(a,7);b-=min(b,5);}else if(c==2){//多余2個3×3的箱子時if(b<3)a-=min(a,4*(3-b));a-=min(a,6);b-=min(b,3);}else if(c==3)//多余3個3×3的箱子時
        {if(!b)a-=min(a,4);a-=min(a,5);b-=min(b,1);}num+=ceil(b/9.0);b%=9;if(b)a-=min(a,(9-b)*4);num+=ceil(a/36.0);printf("%d\n",num);}return 0;
}

?

N - Stall Reservations

?

這里有N只 (1 <= N <= 50,000) 挑剔的奶牛! 他們如此挑剔以致于必須在[A,B ]的時間內產奶(1 <= A <= B <= 1,000,000)當然, FJ必須為他們創造一個決定擠奶時間的系統.當然，沒有牛想與其他奶牛分享這一時光?

幫助FJ做以下事:

• 使每只牛都有專屬時間的最小牛棚數
• 每只牛在哪個牛棚

也許有很多可行解。輸出一種即可，采用SPJ

Input

第一行一個數字 N?

第 2..N+1行: 第 i+1行 描述了i號奶牛擠奶的起止時間

Output

第一行：牛棚最小數量?

Lines 2..N+1: 第 i+1行 描述了i奶牛被安排的牛棚

Sample Input

5
1 10
2 4
3 6
5 8
4 7

Sample Output

4
1
2
3
2
4

Hint

樣例解釋：?

這里是一種圖示?

Time     1  2  3  4  5  6  7  8  9 10

Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>

Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..

Stall 3 .. .. c3>>>>>>>>> .. .. .. ..

Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

其他的也是可能的

?　　思路：這是一道牛奶分欄問題，分欄不算難，難點在于如何描述某只奶牛在哪個牛棚中。有兩種貪心策略，一：以最早開始的奶牛進行計算，在該奶牛產奶結束后

選取離這個結束時間最近且的奶牛，安排其進行產奶，直至某個牛的結束時間大于或等于規定時間，開始為下一個牛棚安排；這種策略實際上是以牛棚為出發點，通過使用最少的牛棚讓更多的牛產奶，直到所有奶牛都產過奶了；實現要用set或數組，進行一個牛棚的安排后，要對在該牛棚產奶的牛進行刪除。二：將奶牛以產奶時間的早晚進行排列，在時間順序上讓每一個奶牛在產奶時間都能有牛棚產奶，若有空閑牛棚，則安排改產奶的奶牛去產奶，若是沒有空閑牛棚，就要準備新的牛棚；通過優先隊列以及對隊列的維護實現。這里我是用了優先隊列，實現代碼如下：

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#define LL long long
int const max_n=50002;
using namespace std;
struct Node{int st,ed,id,stal;//開始時間，結束時間，奶牛編號，牛棚號bool operator <(const Node &a)const{//這是優先隊列中一個排序方式，重載＜用來排序，維護優先隊列return a.ed<ed;    }
}cow[max_n];
bool cmp(Node a,Node b)//結構體比較函數
{if(a.st!=b.st)return a.st<b.st;return a.ed<b.ed;
}
int main()
{int n,a[max_n];scanf("%d",&n);priority_queue<Node> q;//下標由1開始，方便計算和思考for(int i=1;i<=n;i++){scanf("%d %d",&cow[i].st,&cow[i].ed);cow[i].id=i;}sort(cow+1,cow+n+1,cmp);cow[0].stal=1,cow[0].ed=0;q.push(cow[0]);int i=1,k=2;//初始化牛棚數為2while(i<=n){Node c=q.top();if(cow[i].st>c.ed)//當某個牛的開始產奶時間大于隊列中最早結束時間，即這個牛產奶開始時有空閑牛棚
        {q.pop();cow[i].stal=c.stal;a[cow[i].id]=c.stal;q.push(cow[i]);}else{//沒有空閑牛棚，安排新牛棚cow[i].stal=k;a[cow[i].id]=k++;q.push(cow[i]);}i++;}printf("%d\n",k-1);for(int i=1;i<=n;i++)printf("%d\n",a[i]);return 0;
}

?

?

O - Yogurt factory

奶牛們收購了一家世界著名的酸奶工廠Yucky Yogurt. 在接下來的 N (1 <= N <= 10,000) 周,牛奶和人工的價格每周會波動，以致于第i周需要花公司 C_i (1 <= C_i <= 5,000) 美分來生產一個單位的酸奶. Yucky factory被奶牛們照顧得很好，所以每周可以生產很多單位的酸奶?

Yucky Yogurt 擁有一個倉庫，可以以S (1 <= S <= 100)美分每單位每周的價格儲存沒用的酸奶。神奇的是，酸奶不會變質。而且倉庫十分巨大，可以容納很多牛奶?

Yucky Yogurt每周要交貨 Y_i (0 <= Y_i <= 10,000) 單位的酸奶給它的客戶。請你幫助奶牛們減少整個 N-week 期間的支出. i周生產的牛奶和之前儲存的牛奶都可以用來交i周的貨

Input

* 第一行：N and S.?

* 第 2..N+1行:第 i+1 行包括 : C_i 和 Y_i.

Output

* 滿足客戶需求的最小花費，保證不超過64位整數

Sample Input

4 5
88 200
89 400
97 300
91 500

Sample Output

126900

Hint

輸出提示:?
第一周生產200單位，全部售出。第二周生產700單位，售出400，儲存300.第三周使用儲存的300單位。第四周，生產500單位并全部售出?
注釋：
yucky意為難以下咽的

?

?　　思路：貪心策略為，在本周的人工成本較低下周時（即生產下周要交貨的奶加上存儲的錢仍比下周生產牛奶價格低時），在本周多生產下周要交貨的牛奶數，并存在倉庫里。其他情況，就老老實實生產足夠本周交貨的奶，因為一般情況下不考慮生產后兩周的牛奶加上存兩周牛奶的錢比下下周的生產成本低的情況。代碼如下：

#include <iostream>
#include <algorithm>
#define LL long long
int const max_n=10002;
using namespace std;
struct node{int c,y;
}num[max_n];
int main()
{int n,s;scanf("%d %d",&n,&s);for(int i=0;i<n;i++)scanf("%d %d",&num[i].c,&num[i].y);int i=0;LL mony=0;while(i<n){if(num[i].c*num[i+1].y+s*num[i+1].y<num[i+1].c*num[i+1].y){mony+=num[i].c*num[i+1].y+s*num[i+1].y;num[i+1].y=0;}mony+=num[i].c*num[i].y;i++;}cout<<mony;return 0;
} 

?

?