【算法】贪心 【难度】★☆☆☆☆
考查贪心和排序。按题意需要找所需木板的最小总长度，若不考虑木板数目的限制，理论上的最短木板就是把所有有牛的牛棚都盖住。所以贪心算法很明显了。由于木板总数有限，所以在盖住所有有牛的牛棚后，找出连续牛棚之间的空隙，将最短空隙连起来，并重复这一过程，直到木板总数达到要求。
View Code
1 /*
2 ID: wsc5001
3 LANG: C
4 TASK: barn1
5 */
6 #include <stdio.h>
7 #include <stdlib.h>
8 int b[200][4]={0},a[201]={0};
9 void quicksort0 (int f,int r)
10 {
11 int i,j;
12 int t0;
13 i=f;
14 j=r;
15 t0=a[i];
16 while (i<j)
17 {
18 while (i<j&&a[j]>t0){j--;}
19 if(i<j)
20 {
21 a[i]=a[j];
22 i++;
23 }
24 while (i<j&&a[i]<t0){i++;}
25 if(i<j)
26 {
27 a[j]=a[i];
28 j--;
29 }
30 }
31 a[i]=t0;
32 if (i-1>f)
33 quicksort0(f,i-1);
34 if (j+1<r)
35 quicksort0(j+1,r);
36 }
37 void quicksort1 (int f,int r)
38 {
39 int i,j;
40 int t0,t1,t2;
41 i=f;
42 j=r;
43 t0=b[i][0];
44 t1=b[i][1];
45 t2=b[i][2];
46 while (i<j)
47 {
48 while (i<j&&b[j][2]>t2){j--;}
49 if(i<j)
50 {
51 b[i][0]=b[j][0];
52 b[i][1]=b[j][1];
53 b[i][2]=b[j][2];
54 i++;
55 }
56 while (i<j&&b[i][2]<t2){i++;}
57 if(i<j)
58 {
59 b[j][0]=b[i][0];
60 b[j][1]=b[i][1];
61 b[j][2]=b[i][2];
62 j--;
63 }
64 }
65 b[i][0]=t0;
66 b[i][1]=t1;
67 b[i][2]=t2;
68 if (i-1>f)
69 quicksort1(f,i-1);
70 if (j+1<r)
71 quicksort1(j+1,r);
72 }
73 void quicksort2 (int f,int r)
74 {
75 int i,j;
76 int t0,t1,t2,t3;
77 i=f;
78 j=r;
79 t0=b[i][0];
80 t1=b[i][1];
81 t2=b[i][2];
82 t3=b[i][3];
83 while (i<j)
84 {
85 while (i<j&&b[j][0]>t0){j--;}
86 if(i<j)
87 {
88 b[i][0]=b[j][0];
89 b[i][1]=b[j][1];
90 b[i][2]=b[j][2];
91 b[i][3]=b[j][3];
92 i++;
93 }
94 while (i<j&&b[i][0]<t0){i++;}
95 if(i<j)
96 {
97 b[j][0]=b[i][0];
98 b[j][1]=b[i][1];
99 b[j][2]=b[i][2];
100 b[j][3]=b[i][3];
101 j--;
102 }
103 }
104 b[i][0]=t0;
105 b[i][1]=t1;
106 b[i][2]=t2;
107 b[i][3]=t3;
108 if (i-1>f)
109 quicksort2(f,i-1);
110 if (j+1<r)
111 quicksort2(j+1,r);
112 }
113 int zhao(int n,int t)
114 {
115 int i;
116 for (i=0;i<=t+1;i++)
117 if(b[i][3]==n)
118 return i;
119 }
120 int main()
121 {
122 FILE *fin,*fout;
123 fin=fopen("barn1.in","r");
124 fout=fopen("barn1.out","w");
125 int m,s,c,i,j,k,t,e;
126 fscanf(fin,"%d%d%d",&m,&s,&c);
127 for (i=0;i<c;i++)
128 {
129 fscanf(fin,"%d",&a[i]);
130 }
131 quicksort0(0,c-1);
132 b[0][0]=a[0];
133 t=0;
134 for (i=0;i<c;i++)
135 {
136 if (i+1<c&&(a[i+1]>(a[i]+1)))
137 {
138 b[t][2]=a[i+1]-a[i]-1;
139 b[t][1]=a[i];
140 b[t+1][0]=a[i+1];
141 t++;
142 }
143 }
144 b[t][1]=a[c-1];
145 b[t][2]=9999;
146 //printf("***%d***\n",t);
147 quicksort1(0,t-1);
148 for (i=0;i<=t;i++)
149 {
150 b[i][3]=i;
151 }
152 quicksort2(0,t-1);
153 if(t+1<=m)
154 k=c;
155 if (t+1>m)
156 {
157 k=c;
158 //printf("%d\n",k);
159 for (i=0;i<t+1-m;i++)
160 {
161 e=zhao(i,t);
162 k+=b[e][2];
163 }
164 }
165 fprintf(fout,"%d\n",k);
166 //system("pause");
167 fclose(fin);
168 fclose(fout);
169 }