存档

文章标签 ‘c++’

上海交通大学08年研究生机试题B

2009年9月23日 没有评论

题目
Problem B. Simple Sorting
Input file: Standard Input
Output file: Standard Output
Time Limit: 1 Second

You are given an unsorted array of integer numbers. Your task is to sort this array and kill possible duplicated elements occurring in it.

Input
The first line of the input contains an integer number N representing the quantity of numbers in this array(1≤N≤1000). Next N lines contain N integer numbers(one number per each line) of the original array.

Output
Output file should contain at most N numbers sorted in ascending order. Every number in the output file should occur only once.

Sample input and output
Standard Input Standard Output
6 3
8 7
8 8
7
3
7
7

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_LEN 1000
 
int number_of_inputs;
int inputs[MAX_LEN];
 
void get_inputs()
{
	int i;
	cin >> number_of_inputs;
	for (i=0;i<number_of_inputs;++i)
	{
		cin >> inputs[i];
	}
}
 
void qsort(int left,int right)
{
	int i = left;
	int j = right;
	int pivot_index = (i + j) / 2;
	int pivot = inputs[pivot_index];
	while (i <= j)
	{
		while (inputs[i] < pivot)
			++i;
		while (inputs[j] > pivot)
			--j;
		if (i <= j)
		{
			int temp = inputs[i];
			inputs[i++] = inputs[j];
			inputs[j--] = temp;
		}
	}
	if (i > left)
		qsort(left,j);
	if (j < right)
		qsort(i,right);
}
int main()
{
	get_inputs();
 
	qsort(0,number_of_inputs-1);
	ofstream output_file;
	output_file.open("output.txt");
	for (int i =0;i<number_of_inputs-1;++i)
	{
		if (inputs[i] != inputs[i+1])
			output_file << inputs[i] << endl;
	}
	if (i == number_of_inputs -1)
		output_file << inputs[i] << endl;
	output_file.close();
	return 0;
}
分类: 算法 标签: , ,