barn1.cpp

USACO chapter one.May hope it useful to someone

/*
ID: chenkai4
PROG: barn1
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("barn1.in");
ofstream out("barn1.out");
int M,S,C;bool hascow[201]={0};int num[201];
int l[201],r[201],sp=1;

int main()
{
	in>>M>>S>>C;int t,count=0,ll=0,lr=0;hascow[0]=false;
	for(int a=1;a<=C;a++)
		in>>num[a];
	for(int a=1;a<C;a++)
		for(int b=a+1;b<=C;b++)
			if(num[b]<num[a])
				{t=num[b];num[b]=num[a];num[a]=t;}
	ll=num[1];hascow[num[1]]=true;lr=num[1];
	for(int a=2;a<=C;a++)
	{
		t=num[a];
		hascow[t]=true;
		if(!hascow[t-1])
		{
			l[sp]=ll;
			r[sp]=lr;
			sp++;
			ll=t;
		}
		lr=t;
	}
	l[sp]=ll;
	r[sp]=lr;

	int answer=0;
	if(sp<=M)
	{
		for(int a=1;a<=sp;a++)
			answer+=r[a]-l[a]+1;
	}
	else
	{
		while(sp!=M)
		{
			int mina=1;
			for(int a=2;a<=sp-1;a++)
				if(l[a+1]-r[a]<l[mina+1]-r[mina])
					mina=a;
			r[mina]=r[mina+1];
			for(int a=mina+1;a<=sp-1;a++)
				{l[a]=l[a+1];r[a]=r[a+1];}
			sp--;
		}
		for(int a=1;a<=M;a++)
			answer+=r[a]-l[a]+1;
	}
	out<<answer<<endl;
	return 0;
}