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
解題思路：這個題想明白一點就好寫了。即螞蟻的速度是一樣的，轉身不消耗時間，那麼可以将兩隻相遇時掉頭的螞蟻，看做交錯而過，不理會相遇即可。因為掉頭與交錯而過的時間是一樣的。再暴力搜素每一個螞蟻的位置，如果是最短時間，則比較
它距杆左邊的距離與距杆右邊的距離取最小，取出最大的最小值，即為所求 。如果是最長時間，比較它與杆左邊的距離與杆右邊的距離取最大，最後取出最大值。代碼如下：
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
#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;
}
解題思路：就是不斷選取最小的兩塊煤進行合成，合成後放入煤堆再找兩個最小的，如果取一次排序一次，時間複雜度太高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做以下事:
- 使每隻牛都有專屬時間的最小牛棚數
- 每隻牛在哪個牛棚
也許有很多可行解。輸出一種即可，采用SPJInput
第一行一個數字 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;//初始化牛棚數為2
while(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
H int
輸出提示:
第一周生産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;
}
![uva11292 勇者鬥惡龍[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)