题目: vv的大哥bluejoy是一个很nb的人,同时她也非常的善良且乐于助人。今年bluejoy拿到了一等奖学金,她得知vv非常穷困潦倒,于是决定给她的好朋友vv买一个全新的kindle,但bluejoy是一个热爱打代码的girl,于是她想考考vv,如果vv能通过她的考验,她就奖励vv一个kindle,如果不能,她就会无情的用她所有的奖学金去买滑板,一毛钱都不留给vv!
vv非常想要这个kindle,你能帮她拿到这个kindle吗!真是太感谢你了!
bluejoy的考验是:她的奖学金有n元,kindle需要m元,是否有可能通过数次删去n中的一位(次数可为0),使得n=m?如果可以,输出删除的次数,如果不可以,则输出impossible!
例如:
1.n=13,m=3,则删除n中的第一位的数字1,此时答案为1。
2.n=2342,m=32,则删除n中的第一位2与第三位4,此时答案为2。
3.n=222,m=32;则不可能删除n中的任何一位或几位使m=n,此时答案为Impossible。
Input: 输入数据包含多组测试实例,输入的第一行包含两个正整数n,m(1<=n<=1018)(1≤m≤1018)
Output: 对于每组数据,如果可以删除,则输出删除的次数,否则输出“Impossible”。
思路: 首先明确一点,答案只会有两个,一个是impossible,一个是n的长度-m的长度。 先用字符数组存n,m,循环读入
char a[20],b[20]; while(~scanf("%s%s",a,b)){接下来我们定义一个head变量,用来指向b数组的下标(不懂为什么要定义head的先往下看)
int head=0;我们先举个例子: N=12365478 M=158
i01234567a[i]12365478b[i]158我们开始进行匹配查询: ①查a[0]和b[0]是否匹配?a[0]=1 , b[head]=b[0]=1 可知 a[0]=b[head],匹配!head++;
②查a[1]和b[1]是否匹配?(为什么不查a[1]和b[0]是否匹配?因为head=1,这说明b[0]已经被匹配过了,head指向的是我当前需要匹配的字符.)a[1]=2 , b[head]=b[1]=5, a[1]!=a[head],不匹配!
③查a[2]和b[1]是否匹配?(同上,b[1]都没匹配完你还想匹配个啥?) a[2]=3 , b[1]=5,不匹配!
④查a[3]和b[1]是否匹配?a[3]=6 , b[1]=5,不匹配!
⑤查a[4]和b[1]是否匹配?a[4]=5,b[1]=5,匹配!head++.
⑥查a[5]和b[2]是否匹配?(看上面哦,b[1]匹配完了,要匹配b[2]了,所以此时head=2) … 一直匹配到最后一位 a[7]=8 , b[3]=8,匹配!head++,此时head=3;
好啦已经全部匹配完了! 那么要怎么看b是否全部成功匹配呢? 代码如下:
if(head==strlen(b)) printf("%d",strlen(a)-head); else printf("Impossible");为什么是这样的呢? 因为:一旦b中的数全部匹配完了,那么head一定走到了最后一个数的后面一个位置。 全部代码如下:
char a[20],b[20]; while(~scanf("%s%s",a,b)){ int head=0; for(int i=0;i<strlen(a);i++){ if(a[i]==b[head]){ head++; } } if(head==strlen(b)) printf("%d",strlen(a)-head); else printf("Impossible");