在一上来动不动就用循环体我就剁手!
「这次练习用的数也太大了吧,我怎么记得住。」线段树小声嘀咕着,「我用所有的手指也只能数到 10231023 。」
「这可不是数据结构会作出的发言。」链表指引着面前的少女把数写进她的本体——一棵二叉树的图样中。有光自最浅的节点倾泻而下。「接下来你应该把这个十进制数按数位拆开,重新排列出一个最大的数,然后算出这个数和原数的差。」她正要问线段树是否听懂了任务,却被线段树的发问打断了。
「上一代数据结构,他们会区间排序,能轻松地击溃那些题目,是这样吗?他们于代码的溪流中降生,在算法的庇佑下抽枝长叶,以天赐的技巧征服了我们一代至今无法涉足的外界,是这样吗?」
链表沉默半晌,转移了话题:「你还不会输出,那便直接告诉我练习的答案对 10 取模的值。」
你对这个种族的历史毫无兴趣,只想知道练习题的答案,也就是说——
对于一个数 nn ,记 mm 为把 nn 的各数位重排序得到的最大的数,求 m-nm−n 对 1010 取模的值(也就是 m-nm−n 除以 10 的余数)。
举例来说,当 n=213 时, 各数位重排序有 123、132、213、231、312、321 六种可能,其中最大的数字是 321 ,所以 m=321,输出的答案即为 (m-n) = 108 对 10 取模的结果,也就是 8。
一行一个整数 n (0 < n < 10106 ,也就是说 n 是位数不超过 10n6 的正整数。)。
一个整数,表示答案。
样例输入 1 | 样例输出 1 |
---|---|
213 | 8 |
样例解释 1 此样例的解释在题目描述里。
样例输入 2 | 样例输出 2 |
---|---|
71806291 | 9 |
样例解释 2 答案为 98762110−71806291=26955819≡9(mod10) 。
样例输入 2 | 样例输出 2 |
---|---|
12345678912345678912345 | 6 |
样例解释 3 请特别注意, n 的值可能非常大,无法用 32-bits 或 64-bits 整数储存。
一看到这个题第一眼我以为就是卡数据想都没想就选了Python用了两个循环就交了,结果当然是WA了,结果卡出1900ms,后来仔细审了下题,因本题数据非常大,而且所求只与数位有关,然后结果就是最大数的最低位(即原数的数位的最小值)和原数最低位的差。这样它的时间复杂度就为O(n)。
num = input()
num = list(num)
for i in num:
i = int(i)
minnum = min(num)
print((int(minnum) - int(num[len(num)-1]))%10)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e7;
int a[N];
int main(){
string s;
cin>>s;
int x=s.size();
int y;
y=s[x-1]-'0';
int minn=0x3f3f3f3f;
for(int i=0;i<s.size();i++)
{
if(s[i]-'0'<minn) minn=s[i]-'0';
}
int p=minn-y;
if(p==0) cout<<0;
else cout<<p+10;
}