题目:
【问题描述】
x轴上从左到右有N个整数,第i个数记为Ci。
对于每个数Ci(1 <= i <= N-2),你需要找出在它右侧的所有数与它的差的绝对值中的第二小的值是多少。
保证N个数互不相同。
【输入格式】
输入文件的第一行包括1个正整数N。
第二行包括N个整数,之间用空格隔开。
【输出格式】
输出文件包括一行,N-2个整数,之间用空格隔开。第i个整数表示数Ci的答案。
【样例输入】
4
7 4 2 5
【样例输出】
3 2
【数据规模与约定】
20%的数据满足,3 <= N <= 1 000.
100%的数据满足,3 <= N <= 100 000, 1 <= Ci <= 109.
为什么我这道倍增的题会错?C++
答案:3 悬赏:20 手机版
解决时间 2021-03-22 22:19
- 提问者网友:寂寞梧桐
- 2021-03-22 00:23
最佳答案
- 五星知识达人网友:洒脱疯子
- 2021-03-22 01:32
第一个种方法
1)取一个数
2)当右边数据个数小于4时转到5
3)当右边数据个数大于4时
取一个数,把数据分割成,比当前数大,小的两部分
4)
当只有大的或小的部分时,选择排序
当一边小于两个数时,另一边选择排序
否则两边选择排序
5)四个数排序,然后选第二小,只有三个数时,三个数排序,选第二小。
6)输出结果
7)如果输出N-2个结果结束,否则,取下一个数回到2)
第2种方法
排序,同时建立索引表
对每一个数取左右个两个共四个数作为候选数,对着这四个数排序取第二小的那个
有一个问题 Ci从哪里来,是在输入里,还是在别的地方,由所给条件可知Ci的个数不超过109-1+1=109个 3<= N<=100 000 有 100000-3+1 =100000-3+1=100002个可见,Ci与N严重不一致,可是当N>109+2时到底的要怎么处理,只输出前109个吗
1)取一个数
2)当右边数据个数小于4时转到5
3)当右边数据个数大于4时
取一个数,把数据分割成,比当前数大,小的两部分
4)
当只有大的或小的部分时,选择排序
当一边小于两个数时,另一边选择排序
否则两边选择排序
5)四个数排序,然后选第二小,只有三个数时,三个数排序,选第二小。
6)输出结果
7)如果输出N-2个结果结束,否则,取下一个数回到2)
第2种方法
排序,同时建立索引表
对每一个数取左右个两个共四个数作为候选数,对着这四个数排序取第二小的那个
有一个问题 Ci从哪里来,是在输入里,还是在别的地方,由所给条件可知Ci的个数不超过109-1+1=109个 3<= N<=100 000 有 100000-3+1 =100000-3+1=100002个可见,Ci与N严重不一致,可是当N>109+2时到底的要怎么处理,只输出前109个吗
全部回答
- 1楼网友:低血压的长颈鹿
- 2021-03-22 03:33
这个题目不是很简单明了吗?????????依次计算第I个数和其右边的差,如样例7输入就为:3,5,2,所以输出是3;4的为2,1,所以输出为2。
整体输出就为:3.2
- 2楼网友:一袍清酒付
- 2021-03-22 02:15
递归都能用栈展开,递归在隐式上就使用了系统栈,所以会爆栈
也可以用循环展开,但是这个不是一定能展开的
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯