#include<iostream>
using namespace std;
int main()
{
int t,n,k;
{
cin>>n>>k;
int a[n+1],pos[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
pos[a[i]]=i;
}
for(int i=1;i<=n;i++)
{
if(!k)
break;
else
{
if(a[i]!=n-i+1)
{
k--;
int temp = a[i];
a[i] = n-i+1;
a[pos[n-i+1]] = temp;
pos[temp] = pos[n-i+1];
pos[n-i+1] = i;
}
}
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
}
- Problem Description
You are given an array of N integers which is a permutation of the first N natural numbers. You can swap any two elements of the array. You can make at most K swaps. What is the largest permutation, in numerical order, you can make?
Input Format:
The first line of the input contains two integers, N and K, the size of the input array and the maximum swaps you can make, respectively. The second line of the input contains a permutation of the first N natural numbers.
Output Format:
Print the lexicographically largest permutation you can make with at most K swaps.
Constraints
1 <= N <= 10^5
1 <= K <= 10^9
- Test Case 1
Input (stdin)5 1
4 2 3 5 1
Expected Output5 2 3 4 1
- Test Case 2
Input (stdin)3 1
2 1 3
Expected Output3 1 2
#include
ReplyDeleteusing namespace std;
int main()
{
int t,n,k;
{
cin>>n>>k;
int a[n+1],pos[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
pos[a[i]]=i;
}
for(int i=1;i<=n;i++)
{
if(!k)
break;
else
{
if(a[i]!=n-i+1)
{
k--;
int temp = a[i];
a[i] = n-i+1;
a[pos[n-i+1]] = temp;
pos[temp] = pos[n-i+1];
pos[n-i+1] = i;
}
}
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
}