Barn Repair(usaco)

/* ID:tianlin2 PROG:barn1 LANG:C++ */ #include <iostream> #include <cstdlib> #include <fstream> using namespace std; int dcmp(const void *va,const void *vb) { //注意是升序排列 return *((int *)vb)<*((int *)va)?1:-1; } int main() { ofstream fout("barn1.out"); ifstream fin("barn1.in"); int m,s,c,mlen=0,x=0; int barn[200],emp[200]; fin>>m>>s>>c; for(int i=0;i!=c;++i) fin>>barn[i]; mlen+=c; qsort(barn,sizeof(int),dcmp); for(int i=0;i!=c-1;++i) { //算出不相连的数字间空多少 if(barn[i]+1!=barn[i+1]) { emp[x]=barn[i+1]-barn[i]-1; ++x; } } //注意此处第二个参数,不是sizeof(emp),而是emp里面被赋值的个数 qsort(emp,x,dcmp); //注意m<=x的条件 if(m<=x) { for(int i=0;i!=x-m+1;++i) mlen+=emp[i]; } fout<<mlen<<endl; //system("pause"); return 0; }

思路是先把牛栏的编号按照升序排列,然后在按顺序算出那些不连续的编号之间空出有几个,把那些空洞放进一个数组,再按照升序排列!

接着再拿住着牛的栏数按照升序加上空洞数目的数组数字,知道剩下的空洞数等于(木板数-1)!

注意考虑木板数大于非空牛栏数的特殊情况!

官方答案:

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define MAXSTALL 200 int hascow[MAXSTALL]; int intcmp(const void *va,const void *vb) { return *(int*)vb - *(int*)va; } void main(void) { FILE *fin,*fout; int n,m,nstall,ncow,i,j,lo,hi,nrun; int run[MAXSTALL]; fin = fopen("barn1.in","r"); fout = fopen("barn1.out","w"); assert(fin != NULL && fout != NULL); fscanf(fin,"%d %d %d",&m,&nstall,&ncow); for(i=0; i<ncow; i++) { fscanf(fin,"%d",&c); //这里用数组保存,省去了排序 hascow[c-1] = 1; } n = 0; /* answer: no. of uncovered stalls */ /* count empty stalls on left */ //应该学会灵活使用for循环中间那个条件 for(i=0; i<nstall && !hascow[i]; i++) n++; lo = i; /* count empty stalls on right */ for(i=nstall-1; i>=0 && !hascow[i]; i--) n++; hi = i+1; /* count runs of empty stalls */ nrun = 0; i = lo; //这里是从左右两边开始算的 while(i < hi) { while(hascow[i] && i<hi) i++; for(j=i; j<hi && !hascow[j]; j++) ; run[nrun++] = j-i; i = j; } /* sort list of runs */ qsort(run,nrun,sizeof(run[0]),intcmp); /* uncover best m-1 runs */ for(i=0; i<nrun && i<m-1; i++) n += run[i]; fprintf(fout,"%d/n",nstall-n); exit(0); }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!