专栏文章
题解:P9080 [PA 2018] Nowy kontrakt
P9080题解参与者 2已保存评论 3
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @miob7jpk
- 此快照首次捕获于
- 2025/12/02 16:21 3 个月前
- 此快照最后确认于
- 2025/12/02 16:21 3 个月前
P9080 [PA 2018] Nowy kontrakt
题目大意
这题我们需要对序列 通过末尾添加数字的方式使其严格单调递增,要求最小化操作次数。难点在于处理不同位数数字间的比较和进位问题。
分析
- 位数多的数字肯定大于位数少的。
- 如果位数相同,那么比较字典序,如果小于前一个数,就在末尾填 。
- 若位数比前一个数少:
- 前导部分更大:补零到相同位数 。
- 前导部分相同:检查剩余位是否需要进位。
- 前导部分更小:补零到相同位数。
上代码!!!
CPP#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;
}
相关推荐
评论
共 3 条评论,欢迎与作者交流。
正在加载评论...