Home > Old Blog Posts > USACO 1.3.2 Barn Repair

USACO 1.3.2 Barn Repair


还是贪心算法。先将数据离散化成一条条长度为1的小木板,每次找当前相距最近,且没有被木板连起来的2个牛棚,并用木板连接,直到不能这样做(即达到了题目的要求)。注意:一开始牛的编号要排序!这里我又沙茶了,题目的数据量决定了这道题用桶排是最合适的。

代码:

/*
ID: dementr1
PROG: barn1
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“barn1.in”);
ofstream fout(“barn1.out”);
int M,S,C;
bool linker[201][201];
bool barn[201];
int cow[201]={};
void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
int partition(int A[],int left, int right)
{
int i=(left+right)/2,j;
swap(&A[i],&A[right]);
i=left-1;
for(j=left;j<right;j++)
{
if(A[j]<A[right])
{
i++;
swap(&A[i],&A[j]);
}
}
i++;
swap(&A[i],&A[right]);
return i;
}
void quicksort(int A[], int left, int right)
{
int i;
if(left<right)
{
i=partition(A,left,right);
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
}
void init()
{
memset(linker,false,sizeof(linker));
memset(barn,false,sizeof(barn));
int i,tmp;
fin>>M>>S>>C;
for(i=0;i<C;i++)
{
fin>>tmp;
barn[tmp]=true;
cow[i]=tmp;
linker[tmp][tmp]=true;
}
}
void work()
{
int time,min,i,tmp1,tmp2,mini,len=0;
for(time=C;time>M;time–)
{
min=999999;
for(i=0;i<C-1;i++)
{
tmp1=cow[i];
tmp2=cow[i+1];
if(tmp2-tmp1<min&&!linker[tmp1][tmp2])
{
min=tmp2-tmp1;
mini=i;
}
}
tmp1=cow[mini];
tmp2=cow[mini+1];
linker[tmp1][tmp2]=true;
len+=tmp2-tmp1-1;
}
fout<<len+C<<endl;
}
int main()
{
init();
quicksort(cow,0,C-1);
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: