時(shí)間限制: 1 s ??空間限制: 128000 KB ??題目等級(jí) : 黃金 Gold 題目描述?Description

在一個(gè)夜黑風(fēng)高,下著暴風(fēng)雨的夜晚,farmer John的牛棚的屋頂、門被吹飛了。 好在許多牛正在度假，所以牛棚沒(méi)有住滿。 牛棚一個(gè)緊挨著另一個(gè)被排成一行，牛就住在里面過(guò)夜。 有些牛棚里有牛，有些沒(méi)有。 所有的牛棚有相同的寬度。 自門遺失以后,farmer John必須盡快在牛棚之前豎立起新的木板。 他的新木材供應(yīng)商將會(huì)供應(yīng)他任何他想要的長(zhǎng)度,但是吝嗇的供應(yīng)商只能提供有限數(shù)目的木板。 farmer John想將他購(gòu)買的木板總長(zhǎng)度減到最少。

給出:可能買到的木板最大的數(shù)目M(1<= M<=50);牛棚的總數(shù)S(1<= S<=200); 牛棚里牛的總數(shù)C(1 <= C <=S);和牛所在的牛棚的編號(hào)stall_number(1 <= stall_number <= S),計(jì)算攔住所有有牛的牛棚所需木板的最小總長(zhǎng)度。 輸出所需木板的最小總長(zhǎng)度作為答案。

輸入描述?Input Description

• 第 1 行: 木板最大的數(shù)目M ,牛棚的總數(shù)S 和 牛的總數(shù)C(用空格分開(kāi))
• 第 2 到 C+1行: 每行包含一個(gè)整數(shù)，表示牛所占的牛棚的編號(hào)。

輸出描述?Output Description

單獨(dú)的一行包含一個(gè)整數(shù)表示所需木板的最小總長(zhǎng)度。

樣例輸入?Sample Input 4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 樣例輸出?Sample Output 25 樣例解釋：

[ 一種最優(yōu)的安排是用板攔牛棚3-8,14-21,25-31,40-43.]

數(shù)據(jù)范圍及提示?Data Size & Hint

見(jiàn)描述

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define MAXN 1001 7 int a[MAXN],m,k,n,s[MAXN],ans; 8 bool cmp(int ta,int tb) 9 { 10 return ta>tb; 11 } 12 int main() 13 { 14 scanf("%d%d%d",&n,&k,&m); 15 if(n>m) 16 { 17 printf("%d\n",m); 18 return 0; 19 } 20 for(int i=1;i<=m;i++) 21 scanf("%d",&a[i]); 22 sort(a+1,a+m+1); 23 for(int i=1;i<=m-1;i++) 24 s[i]=a[i+1]-a[i]; 25 sort(s+1,s+m,cmp); 26 27 for(int i=n;i<=m-1;i++) 28 ans+=s[i]; 29 30 ans+=n; 31 printf("%d\n",ans); 32 33 return 0; 34 }

思路：貪心，輸入數(shù)據(jù)不保證有序，排序之后，舍棄距離最大的N-1個(gè)，然后求和

轉(zhuǎn)載于:https://www.cnblogs.com/suishiguang/p/6028978.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1209 修理牛棚== Codevs 2079 修理牛棚的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。