杭电1106

我就是我 2022-09-11 10:22 84阅读 0赞

#  #

# 排序 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 28373 Accepted Submission(s): 7854**

Problem Description

输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。  
  
你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。

Input

输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。  
  
输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由‘5’组成。

Output

对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。

Sample Input

0051231232050775

Sample Output

0 77 12312320

代码如下：

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    int findSplit(vector<int>& arr, int p, int q)
    {
    	int tmp = arr.at(p) ;
    	while (p < q)
    	{
    		while(p < q && arr.at(q) >= tmp) -- q ;
    		arr.at(p) = arr.at(q) ;
    		while(p < q && arr.at(p) <= tmp) ++ p ;
    		arr.at(q) = arr.at(p) ;
    	}
    	arr.at(p) = tmp ;
    
    	return p ;
    }
    
    void quickSort(vector<int>& arr, int p, int q)
    {
    	if (p < q)
    	{
    		int spIndex = findSplit(arr, p, q) ;
    		quickSort(arr, p, spIndex - 1) ;
    		quickSort(arr, spIndex + 1, q) ;
    	}
    }
    
    void splitInt(string str, char spliter,  vector<int>& ret)
    {
    	ret.clear() ;
    	const char* chs = str.c_str() ;
    	int startIndex = 0 ;
    	while (startIndex < str.length() && chs[startIndex] == spliter) startIndex ++ ;
    
    	while(startIndex < str.length())
    	{
    		int endIndex = startIndex ;
    		while(endIndex < str.length() && chs[endIndex] != spliter) ++ endIndex ;
    		char *tmpStr = new char[endIndex - startIndex + 1] ;
    		memcpy(tmpStr, chs + startIndex, endIndex - startIndex) ;
    		tmpStr[endIndex - startIndex] = '\0' ;
    		ret.push_back(atoi(tmpStr)) ;
    		delete[] tmpStr ;
    		startIndex = endIndex + 1 ;
    		while (startIndex < str.length() && chs[startIndex] == spliter) startIndex ++ ;
    	}
    }
    
    int main(int argc, char** argv)
    {
    	vector<int> testA ;
    	string s ;
    	while(cin >> s)
    	{
    		splitInt(s, '5', testA) ;
    		quickSort(testA, 0, testA.size() - 1) ;
    
    		for (int i = 0; i < testA.size() - 1; ++ i)
    			cout << testA.at(i) << " " ;
    		cout <<testA.at(testA.size() - 1) << endl;
    	}
    	
    	return 0 ;
    }