POJ 2299:Ultra-QuickSort
2024-08-27 08:15:50
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 39397 | Accepted: 14204 |
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence
element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
归并排序。
另外,此题有一坑就是结果会超int32;
详细能够參考:点击打开链接
我写的代码例如以下:
#include<cstdio>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
#include<iostream> using namespace std; const int M = 500000 + 5;
int n, A[M], T[M], i; long long merge_sort(int l, int r, int *A)
{
if (r - l < 1) return 0;
int mid = (l + r) / 2;
long long ans = merge_sort(l, mid, A) + merge_sort(mid + 1, r, A);
i = l;
int p = l, q = mid + 1;
while (p <= mid && q <= r)
{
if(A[p] <= A[q])
T[i++] = A[p++];
else
{
ans += (mid + 1 - p);
T[i++] = A[q++];
}
}
while (p <= mid) T[i++] = A[p++];
while (q <= r) T[i++] = A[q++];
for (int j = l; j <= r; j++)
A[j] = T[j];
return ans;
} int main()
{
int n;
while(scanf("%d", &n) && n)
{
for(int j=0; j<n; j++)
scanf("%d", &A[j]);
printf("%lld\n", merge_sort(0, n - 1, A));
} return 0;
}
最新文章
- 530 User cannot log in, home directory inaccessible.
- cout格式化输出
- Node.js与Sails~Model数据模型
- poj 2337 欧拉回路输出最小字典序路径 ***
- Spark Streaming源码解读之JobScheduler内幕实现和深度思考
- Ajax注册验证用户名是否存在 ——引自百度经验
- php 深入理解addslashes函数
- (三)用Normal Equation拟合Liner Regression模型
- Asp.net自带导出方法
- ubuntu安装python3.5
- iphone下元素放在了一个position: fixed的div中无法点击
- KEEP!
- Laravel (5.5.33) 加载过程(一)
- TMS320DM642学习----第六篇(CCS中.dat文件类型详解)
- MFC 单文档调用对话框
- 解决RAID重启后自动更名为md127
- 关于resin的illegal utf8 encoding at (190)解决方式
- Jmeter压力测试简单教程(包括服务器状态监控)
- 虚拟地址IP
- VIM编辑配置文件基本操作