头像

绊zodiac

中国石油大学(华东




离线:32分钟前


最近来访(1)
用户头像
icebreaker

活动打卡代码 AcWing 788. 逆序对的数量

绊zodiac
3小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N=100010;
int arr[N],tem[N];
long long int ans;
void merge_sort(int arr[],int l,int r)
{
        if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
 int k = 0, i = l, j = mid + 1;
  while (i <= mid && j <= r)
        {
            if (arr[i] <= arr[j]) tem[k ++ ] = arr[i ++ ];
        else 
        {
            tem[k ++ ] = arr[j ++ ];
              ans += (mid - i + 1);
        }
}
  while (i <= mid) tem[k ++ ] = arr[i ++ ];
    while (j <= r) tem[k ++ ] = arr[j ++ ];
   for (i = l, j = 0; i <= r; i ++, j ++ )
    {
        arr[i]=tem[j];
    }
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
        merge_sort(arr,0,n-1);
        cout<<ans;
}


活动打卡代码 AcWing 786. 第k个数

绊zodiac
7小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int q[N];
void quick_sort(int q[],int l,int r)
{
    if(l>=r)return;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);

}

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    cin>>q[i];
    quick_sort(q,0,n-1);
    cout<<q[k-1];
}


活动打卡代码 AcWing 785. 快速排序

绊zodiac
7小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, arr[N];
void quick_sort(int arr[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = arr[l + r >> 1];

    while (i < j)
    {
        do i++; while (arr[i] < x);
        do j--; while (arr[j] > x);
        if (i < j)swap(arr[i], arr[j]);
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);

}



int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << ' ';
    }

}


活动打卡代码 AcWing 787. 归并排序

绊zodiac
7小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

快速排序

···

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N = 100010;
int n, arr[N];
void quick_sort(int arr[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = arr[l + r >> 1];

while (i < j)
{
    do i++; while (arr[i] < x);
    do j--; while (arr[j] > x);
    if (i < j)swap(arr[i], arr[j]);
}
quick_sort(arr, l, j);
quick_sort(arr, j + 1, r);

}

int main()
{
cin >> n;
for (int i = 0; i < n; i)
{
cin >> arr[i];
}
quick_sort(arr, 0, n - 1);
for (int i = 0; i < n; i
)
{
cout << arr[i] << ‘ ‘;
}

···




AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/34224/