《关于出题人写出了一个出题人没法证明正确与否的解法这件事》

RT,lz写出了一个没法证明正确性的贪心

lz想的贪心策略是，每一个数只由后一个数的+1来使得-1最终达到目标状态，实现时分两种情况，一个是直接用，另一个是先改第一个数到目标状态，再从第三个数开始应用。总之就是从前往后，每一个改过的数不再动了

能过数据（~~数据和数据范围都是拿脚做的~~），但是不知道到底对不对，求助万能的谷民们，谢谢

代码如下

CPP

#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;
}

《关于出题人写出了一个出题人没法证明正确与否的解法这件事》

讨论操作

回复

相关推荐

《关于出题人写出了一个出题人没法证明正确与否的解法这件事》