CF779B Weird Rounding

· · 题解

CF779B Weird Rounding

原题链接

分析

一个数能被 10^{k} 整除，即指这个数除以 10^{k} 的值为整数。设这个数为变量 a，得到的整数为 Z，条件可以表示为 a\div 10^{k}=Z，变形得到 a\times 10^{-k}=Z。

我们发现，如果 a 的尾部不是至少连续存在 k 个 0，是无法被 10^{k} 整除的。只要比较处理后的数字尾部连续存在 0 的个数和 k，就能知道是否可以被整除。

思路

既然是从尾部开始找 0，能够想到后进先出的数据结构——栈。将数字以字符串的形式读入，再从高位到低位依次入栈，这样将数字顺序倒了过来，我们只需要判断当前栈顶数字是否为 0，用两个计数器分别记录 0 和非零数字的数量，将对应的计数器累加，再弹出栈顶元素继续判断。

如果当前记录的 0 的数量已经大于等于 k，则删去当前记录的非零数字的数量后可以被整除，输出计数器结束程序。如果直到栈被清空程序仍未被结束，说明只能将数字处理为 0，需要删去除一个 0 外的所有数字。即删去 原数字位数减一 个字符。

Code

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
stack<char>n;
int num,ans;
int main(){
    string q;cin>>q;
    for(int i=0;i<q.length();i++){
        n.push(q[i]); //各数位依次入栈 
    }
    int b=n.size(); //记录数字位数 
    int k;cin>>k;
    while(!n.empty()){ //栈未被清空 
        if(num>=k){ //处理后，被除数大于等于除数尾部0的个数 
            cout<<ans; //能够整除，输出尾部需要删除的非零数字个数 
            return 0;
        } 
        if(n.top()=='0'){
            num++; //数位为0，累加个数 
            n.pop();
        }else{
            ans++; //数位不为0，累加需要删去的个数 
            n.pop();
        }
    }
    //栈空，处理后，被除数小于除数尾部0的个数 
    cout<<b-1; //需要删去除一个0外所有数字 
    return 0;
}