题解：P9080 [PA 2018] Nowy kontrakt

Ymy1201 · 2025-08-16 09:43:18 · 题解

吐槽：我居然是第一篇题解,并且这道题好像还不难。

P9080 [PA 2018] Nowy kontrakt

题目大意

这题我们需要对序列 a 通过末尾添加数字的方式使其严格单调递增，要求最小化操作次数。难点在于处理不同位数数字间的比较和进位问题。

分析

1. 位数多的数字肯定大于位数少的。
2. 如果位数相同，那么比较字典序，如果小于前一个数，就在末尾填 0。
3. 若位数比前一个数少：
   • 前导部分更大：补零到相同位数 +1。
   • 前导部分相同：检查剩余位是否需要进位。
   • 前导部分更小：补零到相同位数。

     上代码！！！

     #include<bits/stdc++.h>
     using namespace std;
     int n;
     long long ans;
     string a,b;
     int main() {
     //  freopen("a.in","r",stdin);
     scanf("%d",&n);
     cin>>a;
     for(int i=2; i<=n; a=b,i++) {
     cin>>b;
     if(a.size()<b.size()||(a.size()==b.size()&&a<b))continue;
     if(a==b) {
         ans++;
         b+='0';
         continue;
     }
     if(a.size()>b.size()) {
         if(a.substr(0,b.size())>b) {
             ans+=a.size()-b.size()+1;
             b+=string(a.size()-b.size()+1,'0');
         } else if(a.substr(0,b.size())==b) {
             string t=a.substr(b.size());
             if(t.find_first_not_of('9')==string::npos) {
                 ans+=a.size()-b.size()+1;
                 b+=string(a.size()-b.size()+1,'0');
             } else {
                 ans+=a.size()-b.size();
                 b=a;
                 for(int j=b.size()-1; j>=0; j--) {
                     if(b[j]=='9')b[j]='0';
                     else {
                         b[j]++;
                         break;
                     }
                 }
             }
         } else {
             ans+=a.size()-b.size();
             b+=string(a.size()-b.size(),'0');
         }
         continue;
     }
     ans+=a.size()-b.size()+1;
     b+=string(b.size()+1-b.size(),'0');
     }
     printf("%lld",ans);
     return 0;
     }

     你不点赞，晚上我就去你家偷马桶盖！