分割排序（排序）- HDU 1106
Problem Description
输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。
你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。
Input
输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。
输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由‘5’组成。
Output
对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。
Sample Input
0051231232050775
Sample Output
0 77 12312320
解题思路：
给定一串字符串数字，例如 513550067，从第一个数循环，然后判断是不是5，如果是，跳到下一个数字3，这时候就把3的下标记为一个假左，然后从3往之后找5（为了防止最后类似0067 找不到5的情况，我把字符串末尾手动加了个字符5）。
找到5 后，下标记为右，然后再把左右下标之间的字符串拿出来判断。
if 它全是由0组成
then 把0存入一个整型数组
else 更新左坐标
从左坐标判断，如果是0，左坐标+1，再判断左坐标，直到这个字符不是0（例如 最后取出的字符串 0067 的左下标对应的是0，右是7，更新左坐标后，左坐标对应的就变成了6，右不变），然后把67字符转换为10进制67存入数组。
最后将数组排序，输出。
源代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<string>
using namespace std;
//快速幂版本
int qpow(int a, int b) {
long long ans = 1;
long long k = a;
while (b) {
if (b & 1)ans = ans * k;
k = k * k;
b >>= 1;
}
return ans;
}
int main()
{
char str[1005];
while (~scanf("%s", str))
{
//存储每个分隔出来的整数
int a[1005];
//z，y分别为每个分隔出来的字符串的左右下标
int i, j, l, z, y, i2;
//c表示a数组存储了多少整数
int c = 0;
z = 0; y = 0;
l = strlen(str);
str[l] = '5';
for (i = 0; i <= l - 1;)
{
if (str[i] != '5')
{
//找到了一个非5数，赋为左下标
z = i;
for (i2 = z + 1; i2 <= l; i2++)
{
if (str[i2] == '5')
{
//从一个非5数，找到第一个字符5.赋为右下标
y = i2 - 1;
//更新i
i = i2 + 1;
break;
}
}
int x, r = 1;
for (x = z; x <= y; x++)
{
if (str[x] != '0')
{r = 2; break;}
}
//判断这个字符串是不是全是0，若是 r为1，不是 r为2；
if (r == 1)
{
//若r为1，a整型数组存入0
a[c] = 0;
c++;
}
else
{
int xx;
for (xx = z; xx <= y; xx++)
{
if (str[xx] != '0')
{
//更新左下标
z = xx;
break;
}
}
int w, w1;
w = y - z + 1;
// w，w1 为此字符串的位数
w1 = w;
int sum = 0, i3, s;
i3 = z;
//将隔出来的字符串 转换为整数10进制赋给sum
while (w--)
{
s = str[i3] - '0';
sum = sum + (s * qpow(10, w1 - 1));
i3++;
w1--;
}
//sum存入数组
a[c] = sum;
c++;
}
}
else
{
i++;
}
}
//排序数组
sort(a, a + c);
for (i = 0; i < c - 1; i++)
{
printf("%d ", a[i]);
}
//按格式输出
printf("%d\n", a[c - 1]);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-03-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读