首页 > 代码库 > usaco-barn-repair-pass-KISS

usaco-barn-repair-pass-KISS

这个应该算比较简洁的了,呵呵,原来是数中间的间隔m-1段,这个思路很有意思:

/*ID: qq104801LANG: C++TASK: barn1*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <assert.h>/* for debug only:counter*/void debug_dummy(void){    return;}int m,s,c;int bb[200],cc[200];int cmpa(const void *a,const void *b){    return *(int*)a - *(int*)b;}int cmpd(const void *a,const void *b){    return *(int*)b - *(int*)a;}int test(void){    int total,i;        if(m>=s)       return c;    else   {            cc[0]=0;                for(i=1;i<c;i++)            cc[i]=bb[i]-bb[i-1]-1;        qsort(cc,c,sizeof(cc[0]),cmpd);        //for(i=0;i<c;i++)            //printf("%d\n",cc[i]);        total=bb[i-1]-bb[0]+1;        //printf("%d\n",total);       for(int i=0;i<m-1;i++)                   total-=cc[i];                  }   return total;    }main () {        FILE *fin = fopen ("barn1.in", "r");    FILE *fout = fopen ("barn1.out", "w");     fscanf(fin,"%d %d %d",&m,&s,&c);    for(int i=0;i<c;i++)    {        fscanf(fin,"%d",&bb[i]);    }    qsort(bb,c,sizeof(bb[0]),cmpa);    int count=0;    count=test();    //printf("%d\n",count);    fprintf(fout,"%d\n",count);        fclose(fin);    fclose(fout);    exit (0);}

测试用例:

USER: ll tom [qq104801]TASK: barn1LANG: C++Compiling...Compile: OKExecuting...   Test 1: TEST OK [0.005 secs, 3496 KB]   Test 2: TEST OK [0.003 secs, 3496 KB]   Test 3: TEST OK [0.003 secs, 3496 KB]   Test 4: TEST OK [0.005 secs, 3496 KB]   Test 5: TEST OK [0.008 secs, 3496 KB]   Test 6: TEST OK [0.003 secs, 3496 KB]   Test 7: TEST OK [0.003 secs, 3496 KB]   Test 8: TEST OK [0.008 secs, 3496 KB]   Test 9: TEST OK [0.003 secs, 3496 KB]   Test 10: TEST OK [0.003 secs, 3496 KB]All tests OK.Your program (‘barn1‘) produced all correct answers! This is your submission #2 for this problem. Congratulations!Here are the test data inputs:------- test 1 ----4 50 17346814151617252627303140414243------- test 2 ----2 10 42468------- test 3 ----3 27 1623568910131415161920212227------- test 4 ----1 200 810110510210610310710499------- test 5 ----50 200 10186919538732861725399------- test 6 ----50 30 630252015105------- test 7 ----20 200 8065178647018328890982015231118117127811757313616116563130133190104138200431893786182145110671261141539925155119176554819762147125601223112962712235503649149108100188771916121166132829515089224012856------- test 8 ----4 200 1007218046198196131165112521331879357351286512713012498815512219310116498143541493884451397916102201415018833176135298019741111495185137593218966671919177134181072008135524142184176109105431818594151160115251161113710414497901411201191521821231724023------- test 9 ----20 195 10012345111213141521222324253132333435414243444551525354556162636465717273747581828384859192939495101102103104105111112113114115121122123124125131132133134135141142143144145151152153154155161162163164165171172173174175181182183184185191192193194195------- test 10 ----1 200 21200Keep up the good work!Thanks for your submission!

 

usaco-barn-repair-pass-KISS