UVA441题解

zwy__ · 2023-04-03 13:51:00 · 题解

题目意思

有 k 个数，你要从中选取 6 个数，并按字典序输出全部的排列。当 k 为 0 时程序结束。

题目思路

根据题目思路进行 dfs 即可。

首先，定义两个变量，一个用来记录枚举到的数的位置，另一个用来记录枚举到的数的编号。假设数的位置为 wz，枚举到的数的编号为 sy。

第二步，记录一个答案数组为 ans。假设给出的 k 个数用 a 数组存储，那么 ans 数组则记录为 ans_{sy}=a_{wz}。

第三步，确认递归条件。因为我们的 sy 初始赋值为 1，所以当 ans 数组完成后，sy 的值应该就是 7。除了完成的答案数组，如果碰到还要选出数的个数不足的情况，我们要进行特判，以免答案中出现错误情况。这个条件是，当 wz+(6-sy) \ge k，就要推出递归。

题目细节

UVA 测评系统特别恶心。

• 在答案的每一行的行末，都不能有空格出现。
• 每一组数据后都要加一个空格。

针对以上这些情况，我们要进行特判，防止格式错误。我就因为这个错了三四次。

正确代码

#include<bits/stdc++.h>
using namespace std;
int n,t;
int a[15],b[15];
void dfs(int wz,int sy)
{
    if(sy==7)//符合情况，输出答案 
    {
        for(int i=1; i<=6; i++)
        {
            cout<<b[i];
            if(i<6)cout<<" ";//特判格式情况 
        }
        cout<<endl;
    }
    if(wz+(6-sy)>n)return ;//判断推出递归条件 
    for(int i=wz; i<=n; i++)//递归 
    {
        b[sy]=a[i];
        dfs(i+1,sy+1);
    }
}
int main()
{
    while(true)
    {
        cin>>n;
        if(n==0)return 0;
        //特判格式情况 
        if(t==1)cout<<endl;
        t=1;
        for(int i=1; i<=n; i++)cin>>a[i];
        dfs(1,1);
    }
    return 0;
}