欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷:P1706 全排列问题(普及-,)

程序员文章站 2024-03-04 10:51:17
...

题目:

洛谷:P1706 全排列问题(普及-,)

分析:首先,当然是用next_permutation水一下啦!

next_permutation

next_permutation

next_permunation

next_permutation

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int n;
 cin>>n;
 int A[n];
 for(int i=0;i<n;i++) A[i]=i+1;
 do{
  for(int i=0;i<n;i++) cout<<"     "<<A[i];
  cout<<endl;
 }while(next_permutation(A,A+n));
}

不用函数:

在leetcode上貌似做过,思路只有一点印象了。

一种贪心吧,当然是尽可能的从后面选:

如果是降序,那么这些数一定不能再小了。

2,5,4,3,1

选比2大的,然后后面从小向大排序。

有点激动啊,代码质量终于有了提升。

先排序,然后用到了upper_bound()找大的。然后后面的又灵活的不借助辅助空间直接移动:

代码:

#include<bits/stdc++.h>
using namespace std;
int B[10];
int main()
{
 int n;
 cin>>n;
 int A[n];
 for(int i=0;i<n;i++) A[i]=i+1;
 while(1)
 {
  int ok=1;
  for(int i=0;i<n;i++) 
  {
   cout<<"    "<<A[i];
   if(A[i]!=n-i) ok=0;
  }
  cout<<endl;
  if(ok) break;
  int c;
  for(int i=n-2;;i--)
  {
   if(A[i]>A[i+1]) continue;
   c=i;
   break;
  }
  int cc=A[c];
  sort(A+c,A+n);
  int k=upper_bound(A+c,A+n,cc)-A;
  int kk=A[k];
  while(1)
  {
   if(k==c) break;
   A[k]=A[k-1];
   k--;
  }
  A[k]=kk;
 }
}
相关标签: 暴力枚举