Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 32487 | Accepted: 11581 |
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 Ultra-QuickSort produces the output
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.
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
#include<iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 500005;
typedef struct Node
{
int pos;
int value;
}Node;
Node node[MAXN];
int tree[MAXN], temp[MAXN];//离散化
int n;
bool cmp(Node a, Node b)
{
return a.value < b.value;
}
int lowbit(int x)
{
return x & (-x);
}
int getsum(int pos)
{
int sum = 0;
while (pos > 0)
{
sum += tree[pos];
pos -= lowbit(pos);
}
return sum;
}
void update(int pos, int value)
{
while (pos <= n)
{
tree[pos] += value;
pos += lowbit(pos);
}
}
int main()
{
//freopen("in.txt", "r", stdin);
long long ans;
while(scanf("%d", &n) != EOF)
{
if(n == 0)
{
break;
}
ans = 0;
for (int j = 1; j <= n; j++)
{
scanf("%d", &node[j].value);
node[j].pos = j;
}
sort(node + 1, node + n + 1, cmp);
for (int j = 1; j <= n; j++)
{
temp[node[j].pos] = j;
}
memset(tree, 0, sizeof(tree));
for (int j = 1; j <= n; j++)
{
update(temp[j], 1);
ans += j - getsum(temp[j]);
}
printf("%lld\n", ans);
}
return 0;
}
Brainman
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 7704 | Accepted: 4199 |
Description
Background
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.
Problem
Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:
Start with: 2 8 0 3
swap (2 8) 8 2 0 3
swap (2 0) 8 0 2 3
swap (2 3) 8 0 3 2
swap (8 0) 0 8 3 2
swap (8 3) 0 3 8 2
swap (8 2) 0 3 2 8
swap (3 2) 0 2 3 8
swap (3 8) 0 2 8 3
swap (8 3) 0 2 3 8
So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:
Start with: 2 8 0 3
swap (8 0) 2 0 8 3
swap (2 0) 0 2 8 3
swap (8 3) 0 2 3 8
The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.
Problem
Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:
swap (2 8) 8 2 0 3
swap (2 0) 8 0 2 3
swap (2 3) 8 0 3 2
swap (8 0) 0 8 3 2
swap (8 3) 0 3 8 2
swap (8 2) 0 3 2 8
swap (3 2) 0 2 3 8
swap (3 8) 0 2 8 3
swap (8 3) 0 2 3 8
So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:
swap (8 0) 2 0 8 3
swap (2 0) 0 2 8 3
swap (8 3) 0 2 3 8
The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.
Input
The first line contains the number of scenarios.
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.
Output
Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence.
Terminate the output for the scenario with a blank line.
Sample Input
4 4 2 8 0 3 10 0 1 2 3 4 5 6 7 8 9 6 -42 23 6 28 -100 65537 5 0 0 0 0 0
Sample Output
Scenario #1: 3 Scenario #2: 0 Scenario #3: 5 Scenario #4: 0
#include<iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 1005;
typedef struct Node
{
int pos;
int value;
}Node;
Node node[MAXN];
int tree[MAXN], temp[MAXN];//离散化
int n;
bool cmp(Node a, Node b)
{
if(a.value == b.value)
{
return a.pos < b.pos;
}
return a.value < b.value;
}
int lowbit(int x)
{
return x & (-x);
}
int getsum(int pos)
{
int sum = 0;
while (pos > 0)
{
sum += tree[pos];
pos -= lowbit(pos);
}
return sum;
}
void update(int pos, int value)
{
while (pos <= n)
{
tree[pos] += value;
pos += lowbit(pos);
}
}
int main()
{
freopen("in.txt", "r", stdin);
int t, ans;
scanf("%d", &t);
for(int i = 1; i <= t; i++)
{
scanf("%d", &n);
ans = 0;
for (int j = 1; j <= n; j++)
{
scanf("%d", &node[j].value);
node[j].pos = j;
}
sort(node + 1, node + n + 1, cmp);
for (int j = 1; j <= n; j++)
{
temp[node[j].pos] = j;
}
memset(tree, 0, sizeof(tree));
for (int j = 1; j <= n; j++)
{
update(temp[j], 1);
ans += j - getsum(temp[j]);
}
printf("Scenario #%d:\n", i);
printf("%d\n\n", ans);
}
return 0;
}
if(a.value == b.value)
{
return a.pos < b.pos;
}离散化，很多网上的代码都没有这一句，我觉得AC，仅仅是数据弱（或者是没有相同的元素），含有相同的元素时，离散化就出问题了。