好贷网好贷款

USACO 4.2.4/cowcycle

发布时间:2016-12-3 12:46:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"USACO 4.2.4/cowcycle",主要涉及到USACO 4.2.4/cowcycle方面的内容,对于USACO 4.2.4/cowcycle感兴趣的同学可以参考一下。

#include <stdio.h> #include <stdlib.h> #include<string.h> int f,r; //前后轮的齿数 int f1,f2; int r1,r2; //后轮的范围 double min=1000000; int ansf[100]={0}; //处理过程中前轮齿数 int ansr[100]={0}; double ratio[100]={0}; int num; double tim; int finaf[100]={0}; //最后保存前轮齿数的答案 int finar[100]={0}; void sort(double *a,int n) //用插入排序速度更快 { int i,j; double key; for(i=1;i<n;i++) { key=a[i]; j=i-1; while(j>=0&&key<a[j]) { a[j+1]=a[j]; j--; } a[j+1]=key; } } double disp(double *a,int m) //求方差 { int i ; double af[100]={0}; double ave=0,var=0; sort(a,m); for(i=0;i<m-1;i++) { af[i]=a[i+1]-a[i]; ave+=af[i]; } ave/=(m-1); for(i=0;i<m-1;i++) { var+=(af[i]-ave)*(af[i]-ave); } return var; } void deal(int m,int n,int front,int rear) //相当于一个dfs过程 { int i ,j; if(m<=f-2) { if(front>ansf[f-1]+m+1-f) return; for(i=front;i<=ansf[f-1]+m+1-f;i++) { ansf[m]=i; deal(m+1,n,ansf[m]+1,ansr[n]); //注意四个参数的值 ,有的不用加1 } } if(n<=r-2) { if(rear>ansr[r-1]+n+1-r) return; for(j=rear;j<=ansr[r-1]+n+1-r;j++) { ansr[n]=j; deal(m,n+1,ansf[m],ansr[n]+1); } } if(m>f-2&&n>r-2) { num=0; for(i=0;i<f;i++) for(j=0;j<r;j++) ratio[num++]=ansf[i]/(ansr[j]*1.0); tim=disp(ratio,num); if(min>tim) { min=tim; memcpy(finaf,ansf,sizeof(ansf[0])*f); memcpy(finar,ansr,sizeof(ansr[0])*r); } } } int main() { FILE *fin=fopen("cowcycle.in","r"); FILE *fout=fopen("cowcycle.out","w"); fscanf(fin,"%d %d",&f,&r); fscanf(fin,"%d %d",&f1,&f2); fscanf(fin,"%d %d",&r1,&r2); int i ,j,k,t; for(i=f1;i<=f2-f+1;i++) for(j=i+f-1;j<=f2;j++) for(k=r1;k<=r2-r+1;k++) for(t=k+r-1;t<=r2;t++) { ansf[0]=i;ansf[f-1]=j; ansr[0]=k;ansr[r-1]=t; if(ansf[f-1]*ansr[r-1]>=3*ansf[0]*ansr[0]) //用乘法法速度更快 { deal(1,1,ansf[0]+1,ansr[0]+1); } } for(i=0;i<f-1;i++) fprintf(fout,"%d ",finaf[i]); fprintf(fout,"%d\n",finaf[f-1]); for(i=0;i<r-1;i++) fprintf(fout,"%d ",finar[i]); fprintf(fout,"%d\n",finar[r-1]); return 0; } 题目不麻烦,就是那个插入排序要注意点

上一篇:数据结构学习笔记(1.大O表示法和顺序表)
下一篇:面试题tx待续

相关文章

相关评论