這題是我們學(xué)校從USACO盜的，正所謂洋為我用。
還有就是我發(fā)現(xiàn)C++博客挺快的，比其它網(wǎng)快多了。
算法：
1，首先把兩頭沒牛的刪去，這樣所有有牛的都在i，j的范圍內(nèi)
2，計算間隔的個數(shù)cnt_val并按大小排序，牛群的個數(shù)cnt_cows等于間隔個數(shù)加1，所謂牛群就是一片一片的牛的個數(shù)，比如5 6 7三個都有牛，算一個群
3，比較，如果牛群個數(shù)小于m，直接輸出牛的個數(shù)（不是牛群）
如果牛群大于M
{length=j-i+i;（整個范圍）
首先，用一快木板把所有的牛都覆蓋了
* 如果木板有剩余，加一塊木板，然后length減去最大的間隔；
*共執(zhí)行m-1次
}
題目地址：
http://icpc.ahu.edu.cn/AOJ/showproblem?problem_id=1187 代碼：
1
#include<iostream>
2#include<algorithm>
3#include<vector>
4#include<string.h>
5using namespace std;
6int main()
7
{
8
int a[205];
9 int b[205];
10 memset(b,0,205*sizeof(int));
11 memset(a,0,205*sizeof(int));
12 int i, m,s,c,ival,j,length,cnt_cows,cnt_val,cnt,p;
13 cin>>m>>s>>c;
14 for(i=1;i<=c;i++)//下標(biāo)從1開始
15
{
16 cin>>ival;
17 a[ival]=1;
18
}
19 i=1;
20 while(a[i]==0)
21 i++;//牛的起始下標(biāo)
22 j=s;
23 while(a[j]==0)
24 j--;//牛的終止下標(biāo)
25 p=1;
26 for(int k=i+1;k<=j;)
27 {
28 cnt=0;
29 if(a[k]==1)
30 k++;
31 if(a[k]==0&&a[k-1]==1&&k<=j)
32 {
33 while(a[k]==0)
34 {cnt++;k++;}
35 if(cnt!=0)
36 b[p++]=cnt;
37 }
38 }
39 p=p-1;//p為間隔數(shù)
40 cnt_val=p;
41 cnt_cows=cnt_val+1;
42 sort(b+1,b+1+p);
43 length=j-i+1;
44 if(cnt_cows<=m)
45 cout<<c<<endl;
46 else
47 {
48 for(int q=1;q<=m-1;++q)
49 length-=b[p--];
50 cout<<length<<endl;
51 }
52
53 return 0;
54
}