华为挑战赛
建议看我们队长的2023CCPC华为云挑战赛 C-装箱问题 - 凉宫景 - 博客园 (cnblogs.com)
题目说是有台计算机对于绝对值差小于2 的两个数的大小判断会出错误,现在要求对1-n判断两轮小于i的数,然后做差绝对值.给出绝对值序列,问是否是这个计算机做的.
做的时候被一个发现的"规律"困住了.然后一直wa.尽管已经发现这个的产生方式了.
思路:这个计算机对于绝对值差小于2的数大小比较会出错,那么对其他的都不会出错.在不出错的情况下,每一轮的序列值应该是 0,1,2,3,.....n-1.但是因为会出错,序列值可能会发生改变,但是错误仅仅发生在相邻的两个元素之间.
那么我们可以用0,1,1,1,1,1....1来表示这个序列.一共有n-1个1,表示它比前面的大.如果机器判断2<1,那么序列就会变成0,2,0,1,,,,,,,1换言之就是这个1可以往前借
我们按照给定的序列跑一遍看看形成的两个序列的差的绝对值是否等于给定序列即可
查看代码
#include<iostream>
using namespace std;
int n,a[1000005],b[1000005],c[1000005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>c[i];
//预先分配两个序列
a[1]=b[1]=0;
for(int i=2;i<=n;i++)a[i]=b[i]=1;
for(int i=1;i<n;i++)//第n位没法借了
{
if(abs(a[i]-b[i])<c[i])//向后借位
{
if(a[i]<b[i])//大的+1
{
b[i]++;
b[i+1]--;
}
else a[i]++,a[i+1]--;
}
else if(abs(a[i]-b[i])>c[i])//向后借位
{
if(a[i]<b[i])//小的+1
{
a[i]++;
a[i+1]--;
}else
{
b[i]++;
b[i+1]--;
}
}
}
for(int i=1;i<=n;i++)
{
if(abs(a[i]-b[i])!=c[i])
{
cout<<"NO";
return 0;
}
}
cout<<"YES";
return 0;
}