资源描述
#include#include#includeusing namespace std;int main() int n,i,x10001,y10001; int x_sum,y_sum; while(cinn) for(i=0;ixiyi; sort(x,x+n); sort(y,y+n); for(i=0;in;i+) xi-=i; sort(x,x+n); x_sum=0;y_sum=0; for(i=0;in;i+) x_sum+=abs(xi-xn/2); y_sum+=abs(yi-yn/2); cout(x_sum+y_sum)endl; return 0;/士兵站队问题#include using namespace std; int main() /两个数组 int len = 0; /获取数组的长度 cinlen; /动态分配数组 int * a; int * b; a = (int *)malloc(sizeof(int) * len); b = (int *)malloc(sizeof(int) * len); /获取每个数组的元素 for(int i=0; i ai; for(int j=0; j bj; /两个数组的左右端点的坐标 int aLeft = 0; int aRight = len - 1; int bLeft = 0; int bRight = len - 1; /两数组中间坐标 int aMid = 0; int bMid = 0; /迭代循环 while(true) /printf(a left is %d right is %d, and b left is %d right is %d.n, aLeft, aRight, bLeft, bRight); / 如果两个数组都只剩下两个元素，则中位数一定在其中 if( (aRight - aLeft) = 1 & (bRight - bLeft) = 1) cout=bbLeft)?aaLeft:bbLeft) (aaRight=bbRight)?aaRight:bbRight)endl; / 结束循环 break; else / 求解各个数组的中值 aMid = (int)(aLeft + aRight)/2); bMid = (int)(bLeft + bRight)/2); / 如果A中值小于B中值 if(aaMid bbMid) / 如果B中现存的数列是偶数个，右边值加一 if(bLeft + bRight + 1) % 2 = 0) aLeft = aMid; bRight = bMid + 1; else aLeft = aMid; bRight = bMid; / 如果B中值小于A中值 else / 如果A中现存的数列是偶数个，右边值加一 if(aLeft + aRight + 1) % 2 = 0) aRight = aMid + 1; bLeft = bMid; else aRight = aMid; bLeft = bMid; return 0; /中位数问题 O（logn）时间#include #include using namespace std;int max(int a,int b) if (a=b) return a; else return b;int main() int * *a; int * *b; int n=0; cinn; a=(int * *)malloc(sizeof(int*) * n); int i=0; for(i=1;i=n;i+) ai=(int *)malloc(sizeof(int)*n); /b=(int * *)malloc(sizeof(int) * n); for(i=1;i=n;i+) for (int j=1;jaij; /*for (i=1;i0;i-) for (int j=1;j=i;j+) aij=max(ai+1j,ai+1j+1)+aij; couta11endl; return 0;/数字三角形问题#include using namespace std;int find(int a,int b,int length) a1000;/接受输入的数列 b1000;/保存每一段的最大长度 int max_length=1;/每个子序列的最大长度 int i=0,j=0; int m=0; for(i=0;ilength;i+) bi=1; max_length=1; for(j=0;ji;j+) if(aj= max_length) max_length=bj+1; bi=max_length; if(mn; int a1000; int b1000; int i=0; for(;iai; int result=find(a,b,n); coutresultendl; return 0; /单调递增最长子序列#includeusing namespace std;int main() int n=0,m=0,sum=0; int a10000,b10000; cinn; for(int k=0;kakbk; for(int i=n-1;i1;i-) for(int j=0;jbj+1) m=bj+1; bj+1=bj; bj=m; if(ajaj+1) m=aj+1; aj+1=aj; aj=m; int p=0; for(int f=0;f=n-1;f+) if(afbp) sum+; else p+; coutsumendl; return 0;/会场安排问题#include using namespace std;int greedy(int n,int k,int *m) int sum=0,t=0; for(int i=0;in) return -1; sum+=mi; if(sumn) sum=0; t+; i-; return t;int main() int *m,n,k,result; cinnk; m=new intk+1; for(int i=0;imi; result=greedy(n,k,m); if(result0) coutNo Solution!endl; else coutresultendl; delete m; return 0;/汽车加油问题#include using namespace std; int n,cost=0; int x100,c100100; void work(int i,int count) if(in & countcost) cost = count; if(countcost) for(int j=1;jn; for(int i=1;i=n;i+) for(int j=1;jcij; xi = 0; cost+=cii; work(1,0); coutcostendl; return 0; /工作分配问题（回溯法）#includeusing namespace std;int bestc=0;int bound(int t,int n,int *a,int da)for(t=t+1;tn;t+)da=da+at;if(bestcn-1) if(bestcda) bestc=da;else if(db+btnc;int *a=new intn;int *b=new intn;for(i=0;iai;for(i=0;ibi;int sum=0,value=0;for(int i=1;i=n;i+) sum+=bi;value+=ai;abc(0,n,c,a,b,0,0);coutbestcendl;delete a;delete b;return 0;/背包问题（回溯法）
展开阅读全文