P11059 [入门赛 #27] 数字 (Hard Ver.)题解
Solution
先读题:
在给定x的位数\(n\)和模数\(p\)后,要求构造一个\(x\)在满足\(x\mod p\)的余数尽可能小的前提下使\(x\)的数字尽可能小。
我们假设\(x\)的各位数字之和为\(m\),有\(1\le m\le 9n\)。.
(当\(x\)仅在最高位有1时\(m=1\),称为情况一,当x每位为9时\(m=9n\),称为情况二)
此时对于\(m\)有两种情况:
在\(p> 9n\)或\(p=1\)时无需构造,属于情况一。
\(1<p\le9n\)时需构造,属于情况二,且可以简单证明必定有一个合法\(x\)使\(x\mod p=0\)。
做法:
对于情况二,容易想到一种贪心解法,此时的模数\(p\)可直接看作能在每一位放的所有数字之和,步骤如下:
- 在最高位先放数字1维持\(x\)合法并是\(p\)减1。
- 再从最低位开始放数字,当\(p>=9\)时该位放9且让\(p\)减去9,当\(1\le p\le8\)且不为最高位时使该位为p,接着走向较高的下一位。
- 放置过程中若\(p=0\),那么说明所有数字放完,退出。
- 若在最高位仍有\(p>0\),那么时最高位为\(p+1\)(在步骤一中最高位已经放了1,再加上此时的\(p\))并退出。
复杂度分析:
因为按位放数字,有\(n\)位,复杂度为\(O(n)\),且\(1\le n\le 10^{6}\),该方式可行。
Code
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,p,a[N],idx=1;
int main() {
cin>>n>>p;
if(n*9<p){
putchar('1');
for(int i=1;i<n;++i)putchar('0');
}else{
p--;
while(idx!=n&&p){
if(p>=10)a[idx]=9;
else a[idx]=p;
p-=a[idx];
++idx;
}
a[n]=++p;
for(int i=n;i>=1;--i)cout<<a[i];
}
return 0;
}