Ural 1090. In the Army Now 解题报告
程序员文章站
2023-01-12 23:10:21
利用归并排序求逆序对数,只需要在裸体的归并排序的适当地方加上cnt=n1-i就ok了。很好理解的。
#include
#includ...
利用归并排序求逆序对数,只需要在裸体的归并排序的适当地方加上cnt=n1-i就ok了。很好理解的。
#include<cstdio>
#include<iostream>
using namespace std;
const int maxm=10003;
const int inf=0x7fffffff-1;
int cnt;
// 归并排序中的合并算法
void merge(int array[], int start, int mid, int end)
{
int temp1[maxm/2+1], temp2[maxm/2+1];
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
// 拷贝前半部分数组
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
// 拷贝后半部分数组
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
// 把后面的元素设置的很大
temp1[n1] = temp2[n2] = inf;
// 逐个扫描两部分数组然后放到相应的位置去
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
cnt+=n1-i;//逆序对的个数
array[k] = temp2[j];
j++;
}
}
}
www.2cto.com
// 归并排序
void mergesort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
// 对前半部分进行排序
mergesort(array, start, i);
// 对后半部分进行排序
mergesort(array, i + 1, end);
// 合并前后两部分
merge(array, start, i, end);
}
}
int main()
{
int n,k;
int arr[maxm];
int largemerge=0;
int num;
scanf("%d %d",&n,&k);
for(int j=1;j<=k;j++)
{
cnt=0;
for(int i=0;i<n;i++)
{
scanf("%d",arr+i);
}
mergesort(arr,0,n-1);
if(cnt>largemerge)
{
largemerge=cnt;
num=j;
}
}
printf("%d\n",num);
}
#include<cstdio>
#include<iostream>
using namespace std;
const int maxm=10003;
const int inf=0x7fffffff-1;
int cnt;
// 归并排序中的合并算法
void merge(int array[], int start, int mid, int end)
{
int temp1[maxm/2+1], temp2[maxm/2+1];
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
// 拷贝前半部分数组
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
// 拷贝后半部分数组
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
// 把后面的元素设置的很大
temp1[n1] = temp2[n2] = inf;
// 逐个扫描两部分数组然后放到相应的位置去
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
cnt+=n1-i;//逆序对的个数
array[k] = temp2[j];
j++;
}
}
}
www.2cto.com
// 归并排序
void mergesort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
// 对前半部分进行排序
mergesort(array, start, i);
// 对后半部分进行排序
mergesort(array, i + 1, end);
// 合并前后两部分
merge(array, start, i, end);
}
}
int main()
{
int n,k;
int arr[maxm];
int largemerge=0;
int num;
scanf("%d %d",&n,&k);
for(int j=1;j<=k;j++)
{
cnt=0;
for(int i=0;i<n;i++)
{
scanf("%d",arr+i);
}
mergesort(arr,0,n-1);
if(cnt>largemerge)
{
largemerge=cnt;
num=j;
}
}
printf("%d\n",num);
}
上一篇: Linux 搭建Git服务器的方法
下一篇: SpringMVC架构模拟