[??记录]AT2341 [AGC011E] Increasing Numbers

**题意** ： 称一个十进制数是“递增的”，当且仅当其从高到低的每个数位都不大于下一个数位。 给出数 $n$ ，求其最少能被表示为几个递增的数的和。 $n\leq 10^{500000}$ ，时限 $\texttt{2s}$。 ------------ 十进制下一个递增的数等效于 $9$ 个 $111...111$ (长度可能为零) 的和。 二分答案，转化为判定性问题。 即判定是否有 $p_i$ 使得下式成立 ： $$n=\sum\limits_{i=1}^{9k}\dfrac{10^{p_i}-1}{9}$$ 若成立，说明答案可以 $\leq k$ 。 可以变形为 ： $$9n+9k=\sum\limits_{i=1}^{9k}10^{p_i}$$ 于是，计算出 $9n+9k$ ，然后查看数位和是否 $\leq 9k$ 即可。 需要高精度。 ```cpp #include<algorithm> #include<cstring> #include<cstdio> #define MaxN 500500 using namespace std; int n,t[MaxN],tn; char s[MaxN]; bool chk(int k) { for (int i=1;i<=n;i++)t[i]=(s[i]-'0')*9; t[1]+=k*9; for (int i=1;t[i]||i<=n;i++){ t[i+1]+=t[i]/10; t[i]%=10; } int c=0; for (int i=1;i<=n+50;i++){ c+=t[i]; t[i]=0; } return c<=9*k; } int main() { scanf("%s",s+1); n=strlen(s+1); reverse(s+1,s+n+1); int l=1,r=n,mid; while(l<r){ mid=(l+r)>>1; if (chk(mid))r=mid; else l=mid+1; }printf("%d",l); return 0; } ```