QY20. 冒泡排序
描述
牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。
BubbleSort(a):
Repeat length(a)-1 times:
For every i from 0 to length(a) - 2:
If a[i] > a[i+1] then:
Swap a[i] and a[i+1]
牛牛现在要使用上述算法对一个数组A排序。输入描述
输入包括两行,第一行包括两个正整数n和k(2 ≤ n ≤ 50, 1 ≤ k ≤ 50),表示数组的长度和允许最多的特定操作次数。 第二行n个正整数A[i](1 ≤ A[i] ≤ 1000),表示数组内的元素,以空格分割。输出描述
输出一个整数,表示在执行最多k次特定操作之后,对数组进行上述冒泡排序需要的Swap操作次数。示例1
输入:
3 2 2 3 1
输出:
1
C++ 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2020-12-23
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int i,j,l,n,k,res;
while(cin>>n>>k)
{
vector<int> data(n);
for(i=0;i<n;i++)
cin>>data[i];
vector<vector<int>> ord(n,vector<int>(n,0)),inv(n,vector<int>(n,0));
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
ord[i][j]=ord[i][j-1];
inv[i][j]=inv[i][j-1];
for(l=i;l<j;l++)
{
if(data[l]<data[j])
ord[i][j]++;
else if(data[l]>data[j])
inv[i][j]++;
}
}
}
vector<vector<int>> dp(n,vector<int>(k,0));
for(i=1;i<n;i++)
{
for(j=0;j<k;j++)
{
dp[i][j]=dp[i-1][j]>=(inv[0][i]-ord[0][i])?
dp[i-1][j]:(inv[0][i]-ord[0][i]);
if(j)
{
for(l=1;l<i;l++)
dp[i][j]=dp[i][j]>=(dp[l-1][j-1]+inv[l][i]-ord[l][i])?
dp[i][j]:(dp[l-1][j-1]+inv[l][i]-ord[l][i]);
}
else
{
for(l=1;l<i;l++)
dp[i][j]=dp[i][j]>=(inv[l][i]-ord[l][i])?
dp[i][j]:(inv[l][i]-ord[l][i]);
}
}
}
res=inv[0][n-1]-dp[n-1][k-1];
cout<<res<<endl;
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 404KB, 提交时间: 2020-08-05
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int i,j,l,n,k,res;
while(cin>>n>>k)
{
vector<int> data(n);
for(i=0;i<n;i++)
cin>>data[i];
vector<vector<int>> ord(n,vector<int>(n,0)),inv(n,vector<int>(n,0));
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
ord[i][j]=ord[i][j-1];
inv[i][j]=inv[i][j-1];
for(l=i;l<j;l++)
{
if(data[l]<data[j])
ord[i][j]++;
else if(data[l]>data[j])
inv[i][j]++;
}
}
}
vector<vector<int>> dp(n,vector<int>(k,0));
for(i=1;i<n;i++)
{
for(j=0;j<k;j++)
{
dp[i][j]=dp[i-1][j]>=(inv[0][i]-ord[0][i])?
dp[i-1][j]:(inv[0][i]-ord[0][i]);
if(j)
{
for(l=1;l<i;l++)
dp[i][j]=dp[i][j]>=(dp[l-1][j-1]+inv[l][i]-ord[l][i])?
dp[i][j]:(dp[l-1][j-1]+inv[l][i]-ord[l][i]);
}
else
{
for(l=1;l<i;l++)
dp[i][j]=dp[i][j]>=(inv[l][i]-ord[l][i])?
dp[i][j]:(inv[l][i]-ord[l][i]);
}
}
}
res=inv[0][n-1]-dp[n-1][k-1];
cout<<res<<endl;
}
return 0;
}