RT,lz写出了一个没法证明正确性的贪心
题目在这里
lz想的贪心策略是,每一个数只由后一个数的+1来使得-1最终达到目标状态,实现时分两种情况,一个是直接用,另一个是先改第一个数到目标状态,再从第三个数开始应用。总之就是从前往后,每一个改过的数不再动了
能过数据(数据和数据范围都是拿脚做的),但是不知道到底对不对,求助万能的谷民们,谢谢
代码如下
#include <bits/stdc++.h>
using namespace std;
#define N 10
int n,a[N],b[N],ans1,ta[N],ans2;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)ta[i]=a[i];
for(int i=2;i<=n;i++)
{
int dx=(a[i-1]-b[i-1]+10)%10;
a[i]=(a[i]+dx)%10;
a[i+1]=(a[i+1]-dx+10)%10;
ans1+=dx;
}
if(a[n]!=b[n])ans1=114514;
for(int i=1;i<=n;i++)a[i]=ta[i];
ans2=(a[1]-b[1]+10)%10;
a[1]=b[1];
a[2]=(a[2]-rx+10)%10;
for(int i=3;i<=n;i++)
{
int dx=(a[i-1]-b[i-1]+10)%10;
a[i]=(a[i]+dx)%10;
a[i+1]=(a[i+1]-dx+10)%10;
ans2+=dx;
}
if(a[n]!=b[n])ans2=114514;
int ans=min(ans1,ans2);
if(ans==114514)cout<<-1;
else cout<<ans;
return 0;
}