主题：有关USACO1.3的第2个问题求助！
MK
[专家分：110] 发布于 2005-04-15 19:43:00
请问谁知道有关USACO1.3第二题牛棚修理怎么做啊？
附：
输入：牛棚个数（<=200,>0);几个牛棚有牛；板子数；（不限长度）
一下每行输入一个有牛的牛棚号数；
输出：用的最少长度（用完所有板子，板子盖多少个牛棚都行，但有牛的地方都必须盖住，求最小值）。
一牛场的牛棚一面墙都被吹掉了，现有M块木板，不限长度，现有牛的牛棚都必须盖住，板子书小于有牛的牛棚数，求最小值。
回复列表 （共18个回复）
11 楼
zhouweibin [专家分：0] 发布于 2005-09-05 10:29:00
这是我提交已经通过的程序：
/*
ID: zhouwei4
PROG: barn1
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ofstream fout ("barn1.out");
ifstream fin ("barn1.in");
typedef struct dd{
int i,p;
}DD;
void fast_sort(int f,int t,DD data[])
{
int i,j,p;DD k;
if(t-f>=1)
{
k=data[f];i=f;j=t;p=-1;
while(j>i)
{
if(p==1)
{
while(j>i&&data[i].i>=k.i)
i++;
data[j]=data[i];p=-1;
}
else
{
while(j>i&&data[j].i<=k.i)
j--;
data[i]=data[j];p=1;
}
}
data[i]=k;
fast_sort(f,i-1,data);
fast_sort(i+1,t,data);
}
}
int main()
{
int *a,m,s,c,*f,i,k,min=32767,max=0;
DD *b;
fin>>m>>s>>c;
if(m>=c){fout<<c<<endl;return 0;}
f=new int[s+1];
b=new DD[s];
a=new int[m];
for(i=0;i<c;i++)
{
fin>>k;
f[k]=1;
if(k>max)max=k;
if(k<min)min=k;
}
k=0;
for(i=0;i<=s;i++)
{
if(f[i]==1&&k>0)
{
b[k].i=i-b[k-1].p-1;b[k++].p=i;
}
else if(f[i]==1&&k==0)
{
b[k].i=0;b[k++].p=i;
}
}
fast_sort(0,k-1,b);int num=0;
for(i=0;i<m-1;i++)
num+=b[i].i;
num=max-min+1-num;
fout<<num<<endl;
//for(i=0;i<k;i++)
//cout<<b[i].p<<" "<<b[i].i<<endl;
return 0;
}
12 楼
zhouweibin [专家分：0] 发布于 2005-09-05 10:30:00
这是我提交已经通过的程序：
/*
ID: zhouwei4
PROG: barn1
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ofstream fout ("barn1.out");
ifstream fin ("barn1.in");
typedef struct dd{
int i,p;
}DD;
void fast_sort(int f,int t,DD data[])
{
int i,j,p;DD k;
if(t-f>=1)
{
k=data[f];i=f;j=t;p=-1;
while(j>i)
{
if(p==1)
{
while(j>i&&data[i].i>=k.i)
i++;
data[j]=data[i];p=-1;
}
else
{
while(j>i&&data[j].i<=k.i)
j--;
data[i]=data[j];p=1;
}
}
data[i]=k;
fast_sort(f,i-1,data);
fast_sort(i+1,t,data);
}
}
int main()
{
int *a,m,s,c,*f,i,k,min=32767,max=0;
DD *b;
fin>>m>>s>>c;
if(m>=c){fout<<c<<endl;return 0;}
f=new int[s+1];
b=new DD[s];
a=new int[m];
for(i=0;i<c;i++)
{
fin>>k;
f[k]=1;
if(k>max)max=k;
if(k<min)min=k;
}
k=0;
for(i=0;i<=s;i++)
{
if(f[i]==1&&k>0)
{
b[k].i=i-b[k-1].p-1;b[k++].p=i;
}
else if(f[i]==1&&k==0)
{
b[k].i=0;b[k++].p=i;
}
}
fast_sort(0,k-1,b);int num=0;
for(i=0;i<m-1;i++)
num+=b[i].i;
num=max-min+1-num;
fout<<num<<endl;
//for(i=0;i<k;i++)
//cout<<b[i].p<<" "<<b[i].i<<endl;
return 0;
}
13 楼
zhouweibin [专家分：0] 发布于 2005-09-05 10:32:00
这是我提交已经通过的程序：
/*
ID: zhouwei4
PROG: barn1
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ofstream fout ("barn1.out");
ifstream fin ("barn1.in");
typedef struct dd{
int i,p;
}DD;
void fast_sort(int f,int t,DD data[])
{
int i,j,p;DD k;
if(t-f>=1)
{
k=data[f];i=f;j=t;p=-1;
while(j>i)
{
if(p==1)
{
while(j>i&&data[i].i>=k.i)
i++;
data[j]=data[i];p=-1;
}
else
{
while(j>i&&data[j].i<=k.i)
j--;
data[i]=data[j];p=1;
}
}
data[i]=k;
fast_sort(f,i-1,data);
fast_sort(i+1,t,data);
}
}
int main()
{
int *a,m,s,c,*f,i,k,min=32767,max=0;
DD *b;
fin>>m>>s>>c;
if(m>=c){fout<<c<<endl;return 0;}
f=new int[s+1];
b=new DD[s];
a=new int[m];
for(i=0;i<c;i++)
{
fin>>k;
f[k]=1;
if(k>max)max=k;
if(k<min)min=k;
}
k=0;
for(i=0;i<=s;i++)
{
if(f[i]==1&&k>0)
{
b[k].i=i-b[k-1].p-1;b[k++].p=i;
}
else if(f[i]==1&&k==0)
{
b[k].i=0;b[k++].p=i;
}
}
fast_sort(0,k-1,b);int num=0;
for(i=0;i<m-1;i++)
num+=b[i].i;
num=max-min+1-num;
fout<<num<<endl;
//for(i=0;i<k;i++)
//cout<<b[i].p<<" "<<b[i].i<<endl;
return 0;
}
14 楼
dsh761 [专家分：0] 发布于 2006-08-18 10:10:00
哥们,这才是贪心算法
/*
ID: dushuai
LANG: C++
TASK: barn1
*/
#include<stdio.h>
int main(){
FILE *fin,*fout;
int a[200],b[200],d[200];
int m,s,c,k,l,i,j,max,min;
fin=fopen("barn1.in","r");
fout=fopen("barn1.out","w");
fscanf(fin,"%d %d %d",&m,&s,&c);
if(m>=c)
fprintf(fout,"%d\n",c);
else{
int e[m];
for(i=0;i<c;i++)
fscanf(fin,"%d",&a[i]);
for(k=0;k<c;k++)
for(i=1;i<c;i++)
{if(a[i]<a[i-1])
{min=a[i];
a[i]=a[i-1];
a[i-1]=min;}}
for(i=1,j=0;i<c,j<c-1;i++,j++)
b[j]=a[i]-a[i-1];
for(k=0;k<c-1;k++)
d[k]=b[k];
for(k=0;k<c-1;k++)
for(j=1;j<c-1;j++)
{if(d[j]>d[j-1])
{max=d[j-1];
d[j-1]=d[j];
d[j]=max;}}
for(k=0;k<m;k++)
e[k]=d[k];
l=a[c-1]+1-a[0];
for(k=0;k<m-1;k++)
l=l-e[k];
l=l+m-1;
fprintf(fout,"%d\n",l);
}
fclose(fin);
fclose(fout);
}
15 楼
amyhab [专家分：120] 发布于 2006-10-18 20:27:00
明天给你！！！！！！！！！！！！！！
16 楼
amyhab [专家分：120] 发布于 2006-10-19 20:11:00
var
m,s,c,i,j,k,x,max,min,t,y:integer;
a,b:array[1..1000]of integer;
begin
readln(m,s,c);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
min:=201;
max:=0;
for i:=1 to c do
begin
read(x);
if x>max then max:=x;
if x<min then min:=x;
a[x]:=1;
end;
j:=0;
k:=0;
for i:=min to max do
if a[i]=0 then inc(j)
else begin
inc(k);
b[k]:=j;
j:=0;
end;
for i:=1 to k-1 do
for j:=i+1 to k do
if b[i]<b[j] then begin
y:=b[i];
b[i]:=b[j];
b[j]:=y;
end;
t:=max-min+1;
for i:=1 to m-1 do
t:=t-b[i];
write(t);
end.
[em1][em1][em1][em1][em1][em2]
17 楼
贺天行宝 [专家分：2300] 发布于 2006-10-19 21:19:00
{
ID:htx_2001
PROB:barn1
LANG:PASCAL
}
type arr=array[1..210]of longint;
var
a,b:array[1..210]of longint;
first,last,i,j,m,s,c,k,l:longint;
procedure qsort(l,r:longint;var a:arr);
var x,i,j:longint;
begin
if l>=r then exit;
i:=l;j:=r;x:=a[i];
repeat
while (a[j]<=x)and(i<j) do dec(j);
if (a[j]>x)and(i<j) then begin a[i]:=a[j]; inc(i); end;
while (a[i]>=x)and(i<j) do inc(i);
if (a[i]<x)and(i<j) then begin a[j]:=a[i]; dec(j); end;
until i=j;
a[i]:=x;
qsort(l,i,a);qsort(i+1,r,a);
end;
procedure qsorttwo(l,r:longint;var a:arr);
var x,i,j:longint;
begin
if l>=r then exit;
i:=l;j:=r;x:=a[i];
repeat
while (a[j]>=x)and(i<j) do dec(j);
if (a[j]<x)and(i<j) then begin a[i]:=a[j]; inc(i); end;
while (a[i]<=x)and(i<j) do inc(i);
if (a[i]>x)and(i<j) then begin a[j]:=a[i]; dec(j); end;
until i=j;
a[i]:=x;
qsorttwo(l,i,a);qsorttwo(i+1,r,a);
end;
begin
assign(input,'barn1.in');reset(input);
assign(output,'barn1.out');rewrite(output);
readln(m,s,c);
for i:=1 to c do readln(b[i]);
qsorttwo(1,c,b);
first:=b[1];last:=b[c];
for i:=2 to c do
a[i-1]:=b[i]-b[i-1]-1;
qsort(1,c-1,a);
k:=last-first+1;
for i:=1 to m-1 do
dec(k,a[i]);
writeln(k);
close(input);close(output);
end.
18 楼
amyhab [专家分：120] 发布于 2006-10-20 20:45:00
加分[em19][em19]
我来回复
您所在位置：