蓝桥杯 ALGO-52 算法训练 排列问题

栏目: 编程工具 · 发布时间: 6年前

内容简介:问题描述求一个0~N-1的排列(即每个数只能出现一次),给出限制条件(一张N*N的表,第i行第j列的1或0,表示为j-1这个数不能出现在i-1这个数后面,并保证第i行第i列为0),将这个排列看成一个自然数,求从小到大排序第K个排列。数据规模和约定

问题描述

求一个0~N-1的排列(即每个数只能出现一次),给出限制条件(一张N*N的表,第i行第j列的1或0,表示为j-1这个数不能出现在i-1这个数后面,并保证第i行第i列为0),将这个排列看成一个自然数,求从小到大 排序 第K个排列。

数据规模和约定

N<=10,K<=500000

输入格式

第一行为N和K,接下来的N行,每行N个数,0表示不能,1表示能

输出格式

所求的排列

样例输入

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n, k, t, a[10], index[10], cnt = 1;
    vector<pair<int, int> > v;
    cin >> n >> k;
    for (int i = 0; i < n; i++) 
        a[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> t;
            if (t == 0 && i != j) {
                v.push_back({i, j});
            }
        }
    }
    do {
        int flag = 0;
        for (int i = 0; i < n; i++)
            index[a[i]] = i;
        for (int i = 0; i < v.size(); i++) {
            if (index[v[i].second] - index[v[i].first] == 1) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            if (cnt == k) {
                for (int i = 0; i < n; i++)
                    cout << a[i] << ' ';
                break;
            } else {
                cnt++;
            }
 
        }
 
    } while (next_permutation(a, a + n));
    return 0;
}
❤❤点击这里 -> 订阅PAT、蓝桥杯、GPLT天梯赛、LeetCode题解离线版❤❤ 蓝桥杯 ALGO-52 算法训练 排列问题

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

About Face 3 交互设计精髓

About Face 3 交互设计精髓

Alan Cooper、Robert Reimann、David Cronin / 刘松涛 / 电子工业出版社 / 2008-11 / 72.00元

本书是一本数字产品和系统的交互设计指南,全面系统地讲述了交互设计过程、原理和方法,涉及的产品和系统有个人电脑上的个人和商务软件、Web应用、手持设备、信息亭、数字医疗系统、数字工业系统等。运用本书的交互设计过程和方法,有助于了解使用者和产品之间的交互行为,进而更好地设计出更具吸引力和更具市场竞争力的产品。 全书分成3篇:第1篇描述了“目标导向设计”,详细讨论了用户和设计的过程及思想;第2篇讲......一起来看看 《About Face 3 交互设计精髓》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具