codeforces C1. The Great Julya Calendar 解题报告

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

这是第一次参加codeforces比赛(ABBYY Cup 3.0 - Finals (online version))成功AC的题目(n ≤ 106),解题的突破口是: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 ≤ 106      的数,要想得到最少的减法次数,就要每次减去当前数中最大的位数。第一次提交时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[], t;
sprintf(s, "%d", x); // 把整型的x转化为字符串
n = strlen(s);
for (i = ; i < n; i++) // 保证数组s按照从小到大的顺序排序
{
for (j = i+; j < n; j++)
{
if (s[i] > s[j])
{
t = s[i];
s[i] = s[j];
s[j] = t;
}
}
}
sscanf(s, "%d", &a); // 把字符串转化成整型,以便函数返回
return (a % ); // 得到最大的位数
} int main()
{
int n, count, flag;
while (cin >> n)
{
flag = count = ;
while (n >= )
{
n -= get_next(n);
count++;
flag = ;
}
if (flag)
cout << count + << endl; // 加1是因为个位数到0的转化还需一次的count
else if (n == )
cout << "" << endl;
else // 除0以外的个位数
cout << "" << endl;
}
return ;
}
上一篇:php 解决file_put_contents 不生效


下一篇:洛谷 P1059明明的随机数 & P1068分数线划定 & P1781宇宙总统