自动搬运

查看原文

来自洛谷，原作者为

	Ymy1201 一只正在摸鱼的蒟蒻||100%回关||忘关私我||暑假后小学六年级||玩火影Q区44439234846（是个小白）阿玛特拉斯

搬运于2025-08-24 22:45:11，当前版本为作者最后更新于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;
}

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