1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
/*
ID: mytbk921
LANG: C
TASK: barn1
*/
#include <stdio.h>
#define MAXS 200
int main()
{
int MBoards,nStalls,nCows;
int l,r,ngaps,occupied;
int stalls[MAXS+10]={},gaps[MAXS];
int i,j;
FILE *fin=fopen("barn1.in","r");
FILE *fout=fopen("barn1.out","w");
fscanf(fin,"%d%d%d",&MBoards,&nStalls,&nCows);
l=nStalls; r=0; //initial the left&right bound
for (i=0;i<nCows;++i){
fscanf(fin,"%d",&j);
stalls[j]=1;
if (j<l) //update the bound
l=j;
if (j>r)
r=j;
}
fclose(fin);
ngaps=0;
for (i=l;i<=r;i++){
if (!stalls[i]){ //have a gap
for (j=i;!stalls[j];j++)
;
gaps[ngaps++]=j-i;
i=j; //the i will continue
}
}
//selection sort
for (i=0;i<ngaps&&i<MBoards-1;i++){ //select the largest gaps
int max=i; //form gaps[i] to gaps[ngaps-1]
for (j=i+1;j<ngaps;j++){
if (gaps[j]>gaps[max])
max=j;
}
int tmp=gaps[max];
gaps[max]=gaps[i];
gaps[i]=tmp; //swap finished
}
//calculate
occupied=r-l+1;
for (i=0;i<MBoards-1&&i<ngaps;i++)
occupied-=gaps[i];
fprintf(fout,"%d\n",occupied);
return 0;
}
|
