解题思路:将排队看做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 人评分