蓝桥杯 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 算法训练 排列问题

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

查看所有标签

猜你喜欢:

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

Defensive Design for the Web

Defensive Design for the Web

37signals、Matthew Linderman、Jason Fried / New Riders / 2004-3-2 / GBP 18.99

Let's admit it: Things will go wrong online. No matter how carefully you design a site, no matter how much testing you do, customers still encounter problems. So how do you handle these inevitable bre......一起来看看 《Defensive Design for the Web》 这本书的介绍吧!

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具