我正在尝试解决这个SPOJ问题http://www.spoj.com/problems/BAISED/。
我的方法
for all elements in the preferred_position array
if(position>0&&position<=n)
if(position is unoccupied)
allocate position for user
else
reach the first free position in the array
for all elements whose preferred position is already filled
search both directions left,right to find nearest free_position
我尝试了许多测试用例,并把它们弄对了,但我不知道我在哪里失败并得到错误的答案。我基于贪婪标签选择了这个问题,我真的不知道在哪里应用贪婪技术。谁能给点灯吗?
我哪里错了?这是代码ideone.com/O4ood1的链接
阅读您的代码非常痛苦..而您的解决方案也不是100%正确,因为:
可能有很大的数字大于10 ^ 10,您在做什么错-将这样的数字减少一个,直到达到n,您的生命就太短了,无法等待解决方案找到具有如此大数字的测试结果...(如果希望a [i]小于或等于n,为什么不写a [i] = n)
while(t2>n)
{
t2--;
cnt1++;
}
我在同一测试用例上两次运行您的代码,但是在第二次运行中,我更改了测试中给定数字的顺序,您的解决方案显示了不同的答案:
为了方便调试,我删除了读取字符串的方法。所以我提供没有团队名称的测试
首次运行测试:
1个
10
2 3 4 5 6 7 8 9 7 6
您的解决方案显示结果为6(错误答案是什么)
第二轮:让交换掉最后两个数字并得到
2 3 4 5 6 7 8 9 6 7
您的解决方案显示答案为8(幸运的是,这是正确的答案)
假设有两个未放置的数字a [6] = 6和a [9] = 9,并且有两个自由位置1和8,
您的解决方案将采取6走2步权,将会把6在位置8,然后将采取9并且放到位1。
如果从数字的起始位置到目的地绘制线,您会发现9到1的线完全覆盖了6到8的线。
因此,您应尽量避免这种重叠。
现在绘制从6到1以及从9到8的线,没有重叠,这是最佳的。
So to avoid overlapping you can for example to sort rest of your numbers.
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句