（区间相关问题）[USACO]修理牛棚 Barn Repair

一、算法分析

首先选择一个恰覆盖第一头牛到最后一头牛的木板（此时要排序，因为题给的数据不一定是有序的）。然后考虑截取区间的问题，题目要求木板最大数目为s，换言之，就是要截s-1次。（注意这里截一次等于两刀，具体看图）

由贪心原则，算法还是很直观的，显然，在规定木板个数的基础上，我们一定会优先截掉比较大的“连续空位”，比如第一次和第二次的，而对于第三头和第四头之间的那个空位，由于我们的截取次数不够（也就是规定木板数不够），且那个空位相对较小，所以我们就无法进行截取。因而算法很直观了，即对“连续空位”的大小进行排序，优先截取连续空位大的即可。

二、代码及注释

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a;
vector<int> b;
bool cmp_new(int x1,int x2){
	return x1>x2;
}
int main()
{ 

  int m,s,c;
  cin>>m>>s>>c;
  if(m>=c){                         //注意这里有一个特判，当牛的数目小于最大木板数时，可以做到一牛一板 
  	cout<<c;
  	return 0;
	}
  int x;
  for(int i=0;i<c;i++){
  	cin>>x;
  	a.push_back(x);                  //a用来存牛所在的牛棚编号 
	}
  sort(a.begin(),a.end());           //对编号排序（前面算法分析讲过）
	for(int i=0;i<c-1;i++){
		b.push_back(a[i+1]-a[i]-1);      //算出每个“空位”的长度 
	}
	sort(b.begin(),b.end(),cmp_new);
	int ans=a[c-1]-a[0]+1;             //初始板长 
	
	for(int i=0;i<m-1;i++){            //截掉最大的m-1个空位 
		ans-=b[i];               
	}
	cout<<ans;
	return 0;
}

三、作者

Bowen
转载请注明出处，作者水平有限，如有纰漏，敬请斧正。