常用c++算法代码

堆石子游戏的问题（多元Huffman编码）问题描述：在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。编程任务：对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。Input测试数据的第1 行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。Output输出最大总费用和最小总费用，用一空格隔开，每个答案一行。Sample Input7 345 13 12 16 9 5 22Sample Output593 199代码：#include#include#includeusing namespace std;bool cmp(int a, int b) return ab;void Insert(vector &f, int pos, int value) for (int i = f.size() - 1; i pos; i-) fi = fi - 1; fpos = value;int Find(vector f, int value) int pos = f.size() - 1; while (pos = 0 & fpos value) pos-; return pos + 1;int MaxNum(vector f) sort(f.begin(), f.end(); int Max; Max = 0; while (f.size() = 2) int sum = ff.size() - 1 + ff.size() - 2; Max = Max + sum; f.resize(f.size() - 1); ff.size() - 1 = sum; return Max;int MinNum(vector f, int len) sort(f.begin(), f.end(), cmp); int Min; Min = 0; while (f.size() = len) int sum = 0; for (int i = f.size() - 1; i = f.size() - len & i = 0; i-) sum = sum + fi; Min = Min + sum; f.resize(f.size() - len + 1); if (f.size() len) int pos = Find(f, sum); Insert(f, pos, sum); else if (f.size() != 1) ff.size() - 1 = sum; for (int i = 0; i n m) return false; vector f(n); for (int i = 0; i fi; int Max, Min; Max = MaxNum(f); while (f.size() % (m - 1) != 1) f.push_back(0); Min = MinNum(f, m); cout Max Min endl; return true;int main() while (run(); return 0;登山机器人问题问题描述：登山机器人是一个极富挑战性的高技术密集型科学研究项目，它为研究发展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。登山机器人可以携带有限的能量。在登山过程中，登山机器人需要消耗一定能量，连续攀登的路程越长，其攀登的速度就越慢。在对n 种不同类型的机器人作性能测试时，测定出每个机器人连续攀登1米，2米，k 米，所用的时间。现在要对这n个机器人作综合性能测试，举行机器人接力攀登演习。攀登的总高度为m 米。规定每个机器人只能攀登1次，每次至少攀登1 米，最多攀登k 米，而且每个机器人攀登的高度必须是整数，即只能在整米处接力。安排每个机器人攀登适当的高度，使完成接力攀登用的时间最短。编程任务：给定n 个登山机器人接力攀登的总高度m，及每个机器人连续攀登1 米，2 米，k米，所用的时间，编程计算最优攀登方案。Input每组测试数据的第一行是正整数n，k和m分别表示机器人的个数，每个机器人最多可以攀登的高度，和攀登的总高度。接下来的n行中，每行有k 个正整数，分别表示机器人连续攀登1米，2米，k 米所用的时间。Output输出最短攀登时间，每个答案一行。Sample Input5 10 2524 49 75 102 130 160 192 230 270 32023 48 75 103 139 181 224 274 344 41522 49 80 180 280 380 480 580 680 78025 51 80 120 170 220 270 320 370 42023 49 79 118 158 200 250 300 350 400Sample Output727代码：#include#includeusing namespace std;int n,k,m;const int len=100000;int alen;int blen;int main()while(cinnkm) int i; for(i=0; iai; bi=ai; if(i%k!=0) bi=ai-ai-1; sort(b,b+n*k); int sum=0; for(i=0; im; i+) sum+=bi; coutsumendl;return 0;子集和问题问题描述：子集和问题的一个实例为S,c。其中，S=x1，x2，xn是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得 x=c,(xS1)。试设计一个解子集和问题的回溯法。Input测试数据第1 行有2个正整数n和c，n 表示S 的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。其中 n7000 , c10000000 。Output当问题无解时，输出“No”，否则输出“Yes”。Sample Input5 102 2 6 5 411 5311 4 18 10 16 8 4 8 14 22 10Sample OutputYesNo代码：#includeusing namespace std;const int len=7001;int n,c;int alen;int visitlen;int GetRes() int p = 0; int temp = 0; while(p = 0) if(visitp = 0) visitp = 1; temp += ap; if(temp = c) return 1; else if(temp c) visitp = 0; temp -= ap; p+; if(p = n) while(visitp-1 = 1) p-; visitp =0; temp -= ap; if(p 1) return 0; while(visitp-1 = 0) p-; if(p 1) return 0; visitp-1 = 0; temp -= ap-1; return 0;int main()while(scanf(%d%d, &n,&c)!=EOF) memset(visit,0,sizeof(visit); for(int i = 0; i n; i+) scanf(%d, &ai); if(GetRes() printf(Yesn); else printf(Non);return 0;最小重量机器设计问题设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过cost的最小重量机器设计。Input每组测试数据第一行有3 个正整数n，m和cost。接下来的2n行，每行m个数。前n行是cij，后n行是wij。(1=n,m=20; 1=cij =100; 1=wij=100, 1=cost=40000)Output分2行输出最小重量，以及每个部件的供应商。若找不到解决方案，则输出-1。Sample Input3 3 41 2 33 2 12 2 21 2 33 2 12 2 2代码：#include using namespace std; const int len=30;const int maxWeight=4000;int n,m,cost;int wlenlen;/重量int clenlen;/价钱int visitlen;int pathlen;int minWeight = maxWeight;void findMinWeight(int current,int weight,int i) /当前策略的价钱和最小重量 if(i = n) minWeight=weight; for(int j=0; jn; j+) pathj=visitj; return;for(int j=0; jm; j+) if(current+cij=cost & weight+wijnmcost) minWeight = maxWeight; int i,j; for(i=0; i2*n; i+) for(j=0; jm; j+) if(icij; else cinwi-nj; findMinWeight(0,0,0); if(minWeight = maxWeight) cout-1endl; else coutminWeightendl; for(i=0; in; i+) if(i=0) coutpathi; else cout pathi; coutendl; return 0;排列宝石问题问题描述：现有n种不同形状的宝石，每种n颗，共n*n颗。同一种形状的n颗宝石分别具有n种不同的颜色c1, c2, .,cn中的一种颜色。欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。Input每组测试数据为1个正整数n，0n5。Output输出宝石排列方案数Sample Input12Sample Output10代码：#include #include using namespace std; const int len=10;int alenlen;int blenlen;int cclenlen;int ddlenlen;int eelenlen;int n,cnt;void init()for(int i=1; i=n; i+) for(int j=1; j=n; j+) aij=j; bij=j; ccij=0; int ok(int r,int c,int k,int fla)if(fla) if(ccarcbrk) return 0; for(int i=1; ir; i+) if(bic=brk) return 0; else for(int i=1; ir; i+) if(aic=ark) return 0; return 1;void backtrack(int r,int c)for(int i=c; i=n; i+) if(ok(r,c,i,0) swap(arc,ari); for(int j=c; jn) cnt=0; init(); backtrack(1,1); coutcntendl;return 0;多重幂计数问题代码：#includeusing namespace std;_int64 f40;void inits()int i,j;f1=1;for(i=2;i=30;i+) fi=0; for(j=1;jn) return false;printf(%I64dn,fn);return true;int main()inits();while(run();return 0;整数因子分解问题大于1 的正整数n可以分解为：n=x1*x2*xm。例如，当n=12 时，共有8 种不同的分解式：对于给定的正整数n，编程计算n共有多少种不同的分解式。代码：#includeusing namespace std;int cnt;void dfs(int n)for(int i=n-1;i=2;i-) if(n%i=0) cnt+; dfs(n/i); int main()int n;while(cinn) cnt=0; dfs(n); coutcnt+1endl;return 0;旅行规划问题G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。编程任务：对于给定的d0,c,e,p,和n 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。Input每组测试数据的第1 行是d0,c,e,p,和n。接下来的n 行中每行2个数di 和pi。Output输出最小的旅行费用，精确到小数点后2 位。每个答案1行。Sample Input275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2Sample Output26.95代码：#include #include #include using namespace std ;double f100052;double ff100052;bool run()double d,c,e,p;int n,k;if(!(cindcepn) return false;int i,j;ff00=0;ff01=p;for(i=1;iffi0ffi1;ffn+10=d;ffn+11=0;n+;fill(&f00,&f100031,0);double t,x;double y,a2,b,q;for(i=1;i=n;i+) for(j=0;j=t) y=(double)t/e; a0=fj0-y; a1=fj1; q=fj0; else y=(double)(t-x)/e); if(y+fj0c) continue; a0=0; a1=fj1+y*ffj1; q=fj0+y; if(ffj1ffi1) b=(d-ffj0)/e; if(c-q)b) b=c-q; for(k=i+1;k=ffk0) if(ffk1ffj1) b=(ffk0-ffi0)/e; break; else break; a1+=b*ffj1; a0+=b; if(a0=fi0|fi1=0) if(a1fi0) if(a1(a0-fi0)*ffi1+fi1) fi0=a0; fi1=a1; else if(a0fi0) if(a1+(f10-a0)*ffi1fi1) fi0=a0; fi1=a1; if(fn1=0) coutNo Solutionn;else printf(%.2lfn,fn1);return true;int main()while(run();return 0;多处最优服务次序问题问题描述：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1=ti=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小? 平均等待时间是n个顾客等待服务时间的总和除以n。代码：#include#includeusing namespace std;const int lenn=10000;const int lens=500;int n,s;int alenn;int waitlens;int find()int minTime=wait0;int pos=0;for(int i=1; iwaiti) minTime=waiti; pos=i; return pos;int main()while(cinns) int i; for(i=0; iai; sort(a,a+n); memset(wait,0,sizeof(wait); double sum=0; for(i=0; in; i+) int t=find(); waitt+=ai; sum+=waitt; double res=sum/n; printf(%.2fn,res);return 0;可重复最优分解问题问题描述：设n是一个正整数。现在要求将n分解为若干个自然数的和，且使这些自然数的乘积最大。编程任务：对于给定的正整数n，编程计算最优分解方案。Input每组测试数据只有一个正整数n(1=n=10000)。Output输出最大乘积，每个答案一行。（提示：可能是一个非常大的整数！）Sample Input10Sample Output36代码：#include#include#includeusing namespace std;char res10001;int i, carry, len = 1;void mutiply(int n) carry = 0; char *h = res; for (i = 0; i len; i+) *h = *h * n + carry; carry = *h / 10; *h %= 10; h+; if (carry != 0) *h = carry; len+; void f(int n) int n3, n2, i; if (n %2 = 0) n3 = n / 6 * 2; n2 = n % 6 / 2; else n3 = (n - 3) / 6 * 2 + 1; n2 = (n - 3) % 6 / 2; for (i = 1; i 0) mutiply(6); n2-; else mutiply(3); if (n2 0) mutiply(int)pow(2.0,n2); int main() int n; res0 = 1; while(scanf(%d,&n)!=EOF) if (n = 0; i-) printf(%d, resi); printf(n); return 0;有重复元素的排列问题问题描述：设R= r1, r2, ., rn是要进行排列的n个元素。其中元素r1, r2, .,rn可能相同。试设计一个算法，计算出这n 个元素的所有不同排列数。Input每组测试数据首先是n(1=n=500)，接着是待排列的n个元素(小写字母)。Output输出排列总数。Sample Input4 aaccSample Output6代码：#include #include #include using namespace std; const int len=510;int n,ans;char listlen;int ok(int k,int i)if(ik) for(int t=k; ti; t+) if(listt=listi) return 0; return 1;void findResult(int k)if(k=n-1) ans+;else for(int i=k; in) ans=0; for(int i=0; ilisti; findResult(0); coutansendl;return 0;运动员最佳匹配问题问题描述：羽毛球队有男女运动员各n人。给定2个nn矩阵P和Q。Pij是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Qij是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，Pij不一定等于Qji。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为Pij*Qji。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。Input每组测试数据第一行有1个正整数n(1n20)。接下来的2n行，每行n个数。前n行是p矩阵，后n行是q矩阵。Output输出男女双方竞赛优势总和的最大值。Sample Input310 2 32 3 43 4 52 2 23 5 34 5 1Sample Output52代码：#includeusing namespace std;int a22;int p2222;int q2222;int n;int sum=0;void swap(int &x,int &y)int temp=x;x=y;y=temp;void Backtrack(int t)if(tn) int s=0; for(int j=0;j=sum) sum=s;else for(int i=t;in) for(i=0;i=n;i+) ai=i; for(i=0;in;i+) for(j=0;jpij; for(i=0;in;i+) for(j=0;jqij; Backtrack(1); coutsumendl;return 0;半数集问题给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。(1) nset(n)；(2)