題目鏈接：點擊查看

題目大意：設 f( x ) 為 x 的數位之和，給出一個 n 和一個 k ，求??的最小 x ，若不存在，輸出 -1

題目分析：因為 n 和 k 比較小，所以可以打表，當 k 為 0 的時候，顯然是 r + 99...999 是最優的，其中 r = n%9，當 k 為 1 的時候，打表的時間復雜度是 sqrt( 1e16 ) * 8 ，也就是將近 1e9 ，本地可能繃不住，所以可以打到 1e7 左右，然后自己找找規律補齊剩下的幾項就好了，剩下的時間復雜度分別就是?，之類的了，本地輕輕松松搞定

然后說一下正解，因為 k 最大只有 9 ，比較顯然的一點就是，至多會進位一次，因為我們貪心的策略是較低位都放置 9 ，所以個位的進位會涉及到更高位的連續進位，這樣我們不妨設我們最后構造出來的數為 r + 99...999 + 8 + 99..999 + x ，我們將需要構造的數分為了五段，因為說過了，為了貪心，所以低位需要盡量放 9 ，我們設 x 左邊的第一堆 9 的個數為 num_9，又因為如果涉及進位的話，會導致連續進位，所以我們在 num_9 個 9 之前，放置了一個 8 ，到此停止連續進位，剩下的再按照當 k = 0 時貪心放置就好了

因為最多只有 1e16，換句話說 num_9 最多只有 16 ，而個位的 x 也最多只有 9 種取值，我們可以暴力枚舉 x 和 num_9 ，然后計算此時貪心放置得到的最小值，就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=510;int n,k;LL cal(int last,int num_9) {int num=n;for(int i=0;i<=k;i++){if(last+i<=9)num-=last+i+9*num_9;elsenum-=last+i-9;}if(num<0||num%(k+1)!=0)//如果剩下的數小于0了或者不足以恰好分為k+1份，則此時無解return inf;num/=k+1;LL ans=0;if(num<9)//按照k=0時貪心分配即可ans=num;else{num-=8;//別忘了需要放上一個8用來截斷連續的9ans=num%9;for(int i=1;i<=num/9;i++)ans=ans*10+9;ans=ans*10+8;}for(int i=1;i<=num_9;i++)ans=ans*10+9;ans=ans*10+last;return ans; }LL solve() {LL ans=inf;for(int i=0;i<10;i++)//枚舉個位的xfor(int j=0;j<=16;j++)//枚舉x前有多少個9:num_9ans=min(ans,cal(i,j));if(ans==inf)ans=-1;return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d%d",&n,&k);printf("%lld\n",solve());}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1373E Sum of Digits(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。