第五届大学生程序设计竞赛解题报告.ppt

第五届校赛PK赛Description一年一度的厦门理工学院程序设计大赛又开始了，今年是第五届。今年赛会组织方决定用一种新规则决定获胜的选手。在每一轮比赛中，参赛者都是成对的，两两比赛。输者将被淘汰，赢者将自动晋级到下一轮比赛中。比赛一直进行到只剩一个人为止，这个人就是冠军。?在一轮比赛中，如果比赛人数不是偶数，那么将随机选择一个参赛者自动晋级下一轮，而其它人还是一对一地完成本轮比赛。赛会组织方想知道要产生冠军需要进行多少轮比赛。PK赛Input参赛的人数N（1=N=1000000）。Output比赛需要的总轮数。SampleInput15SampleOutput4PK赛思路：n=2^answer搬家的烦恼Description 理工学院的学生每个学年结束以后都要搬宿舍，搬宿舍的烦恼还只是暂时的，搬宿舍以后发现插座不够用是永远的伤痛。? 同学们发现新宿舍只有一个插座，但他们有很多台电脑需要同时使用，于是他们买来了好几个排插，每个排插可支持的插头不一样多，你的任务是帮他们计算一下他们的排插能支持多少台电脑同时使用。（注意：排插本身也需要电源接入）PK赛#includestdio.h#includestring.h#includemath.hintmain(){intn,i=0; scanf(%d,n); while(npow(2,++i)); printf(%d\n,i);return0;}搬家的烦恼Input 输入数据由一个整数N打头（1=N=10），表示接下来测试案例的个数。? 接下来是N行，每行描述了一个测试案例。每个测试案例以一个整数K打头（1=K=10），表示这个测试案例中排插的数量。然后同一行中紧跟着K个整数，中间用空格隔开，O1O2…OK（2=Oi=10）表示每个插座可支持的插头数。Output 每个测试案例对应一行整数输出， 这个整数表示最多能支持的电脑数量。搬家的烦恼SampleInput23234410101010SampleOutput737搬家的烦恼思路：sum=(O1+O2+O3+···+OK)-(n-1)搬家的烦恼#includestdio.h#includestring.h#includemath.hintmain(){intn,i,s,q,z; scanf(%d,n); while(n--){ scanf(%d,q); for(i=1,s=0;i=q;i++){ scanf(%d,z); s+=z; } printf(%d\n,s-q+1); }return0;}木棒还原Description 有N根木棒，现在要把N根木棒还原为一根并且每次只能将两根进行连接，所花费的时间是两根木棒的长度和，要求还原为一根木棒且总时间最短。木棒还原Input 输入数据由一个整数N打头（1=N=100），表示N跟木棒，接下来一行由N个数构成，中间用空格隔开，O1O2…ON（1=Oi=100）表示每根木棒的长度。Output 输出一行正整数，表示还原为一根木棒的最短时间。木棒还原SampleInput3858SampleOutput34木棒还原思路：每次取最小的两根木棒还原。 N根木棒总共需还原的次数为N-1 在总数不变的情况下 使每次时间最短即可 由于要用最短时间 因此 每次计算时间之后排序即可木棒还原#includestdio.h#includestring.h#includemath.hintmain(){ ints[101],q,n,i,j,sum=0; scanf(%d,n); for(i=1;i=n;i++)//输入的同时先进行一次排序 { scanf(%d,s[i]); for(j=i;j1s[j]s[j-1];j--) { q=s[j]; s[j]=s[j-1]; s[j-1]=q; } }木棒还原 while(--n)//做N-1次合并 { sum+=s[n]+s[n+1]; s[n]+=s[n