codeforces C1. The Great Julya Calendar 解题报告

      题目链接：http://codeforces.com/problemset/problem/331/C1

      这是第一次参加codeforces比赛（ABBYY Cup 3.0 - Finals (online version)）成功AC的题目（n ≤ 10⁶），解题的突破口是：Take the magic number, subtract a digit from it (the digit must occur in the number) and get a new magic number. Repeat this operation until a magic number equals zero.

      用到了贪心思想，给出一个  0 ≤ n ≤ 10⁶      的数，要想得到最少的减法次数，就要每次减去当前数中最大的位数。第一次提交时CE（没有包含头文件string.h），第二次和第三次的wa是因为自己太粗心了：对于n为0和除0外的个位数要加个特判。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int get_next(int x)
{
    int a, n, i, j;
    char s[20], t;
    sprintf(s, "%d", x);   // 把整型的x转化为字符串
    n = strlen(s);
    for (i = 0; i < n; i++)    // 保证数组s按照从小到大的顺序排序
    {
        for (j = i+1; j < n; j++)
        {
            if (s[i] > s[j])
            {
                t = s[i];
                s[i] = s[j];
                s[j] = t;
            }
        }
    }
    sscanf(s, "%d", &a);    // 把字符串转化成整型，以便函数返回
    return (a % 10);          // 得到最大的位数
}

int main()
{
    int n, count, flag;
    while (cin >> n)
    {
        flag = count = 0;
        while (n >= 10)
        {
            n -= get_next(n);
            count++;
            flag = 1;
        }
        if (flag)
            cout << count + 1 << endl;  // 加1是因为个位数到0的转化还需一次的count
        else if (n == 0)    
            cout << "0" << endl;
        else                                                    // 除0以外的个位数
            cout << "1" << endl; 
    }
    return 0;
}