原题链接:排队买票
解题思路:将排队看做M人的排列问题,在M!个排列中寻找符合条件的排列(排队时只要一元的人数大于等于2元就有零钱),采用回溯法(深度优先算法)
恭喜我成为继小方之后第二个AC此题的男人
#include <stdio.h> #define N 10 void search(int ); void swap(int ,int ); int a[N]={0}; //待排序数据 int b[N]={0}; //队伍,不大于10 int x=2,y=2,z=4; int count=0; //总次数 int one=0; //已经站队的1元人数 int two=0; //2元人数 int main() { scanf("%d%d%d",&z,&x,&y); int i; for(i=0;i<x;i++) a[i]=1; //一元的小孩为1,两元的为0 for(;i<z;i++) a[i]=0; search(0); printf("%d\n",count); return 0; } void search(int n){ if(n==z){ //队伍站满 count++; //计数 return ; } else{ int j=0; for(j=0;j<z;j++){ if(b[j]==0){ //判断第j人是否已入队 b[j]=1; //第j个人站入 if(a[j]) one++; //站入队伍的为1元 else two++; //站入为2元 if(one>=0 && two>=0 && one>=two)//如果已入队1元大于2元,则有零钱 search(n+1); //判断下一个位置 if(a[j]) one--; else two--; //回溯 b[j]=0; } } } } void swap(int x,int y){ int t=a[x]; a[x]=a[y]; a[y]=t; }
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复