首页 > 代码库 > hdu--1027-next_permutation||dfs
hdu--1027-next_permutation||dfs
....连跪3把 真无语..
写完这个 看电影去了..
明天就去看 后会无期了 应该不会让人失望的
-------------碎碎念
这题 我一开始自己是用 dfs写的.. 后来看了下discuss 看到个新方法 使用stl中的next_permuntation 速度不仅快了许多 而且代码简洁..
关于 这个的介绍 传送
重点 我把它拿出来
next_permutation函数的原理如下：
在当前序列中，从尾端向前寻找两个相邻元素，前一个记为*i，后一个记为*t，并且满足*i < *t。然后再从尾端
寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第t个元素之后（包括t）的所有元
素颠倒排序，即求出下一个序列了。
touch me
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int cnt , n , m; 6 int arr[1010]; 7 bool vis[1010]; 8 9 void dfs(int pos)10 {11 if( cnt==m )12 return;13 if( pos==n )14 {15 cnt++;16 if( cnt==m )17 {18 for( int i = 0 ; i<n-1 ; i++ )19 {20 cout << arr[i] << " ";21 }22 cout << arr[n-1] << endl;23 }24 }25 for( int i = 1 ; i<=n ; i++ )26 {27 if( !vis[i] )28 {29 arr[pos] = i;30 vis[i] = true;31 dfs( pos+1 );32 vis[i] = false;33 }34 }35 }36 37 int main()38 {39 while( cin >> n >> m )40 {41 memset( vis , false , sizeof(vis) );42 cnt = 0;43 dfs(0);44 }45 return 0;46 }
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 int arr[1010]; 6 int main() 7 { 8 int n , m; 9 while( cin >> n >> m )10 {11 for( int i = 0 ; i<n ; i++ )12 {13 arr[i] = i+1;14 }15 while(--m)16 {17 next_permutation(arr,arr+n);18 }19 for( int i = 0 ; i<n ; i++ )20 {21 if(i<n-1)22 cout << arr[i] << " ";23 else24 cout << arr[i] << endl;25 }26 }27 return 0;28 }
today:
在某个阶段，尤其当你寂寞太久的时候，有太多的冲动，把喜欢当成爱，把一秒当成永恒。然而如果不是这么地折腾，你也不会知道自己真的想要的是什么。每个人的青春里都有一条弯路，谁也没法替你走完，但未来总还在。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。