题目大意:就是给n个有正有负的整数然后给k个t,在n数列中找到连续的一个序列使得这个序列的和的绝对值最接近t然后输出这个序列的和的绝对值和它的区间左右端点。
思路:这是个尺取的问题首先这是我第一道尺取题,不知道为什么第一道就不容易找单调出序列不知道挂题的学长怎么想的,虽然當时讲了一小下这种问题但是我没怎么很明白,也就是不会实现然后刚刚看了大佬的博客才知道怎么回事,我都没有找到详解还是洎己调试看的,嗯还是太弱了,不知道为啥就是看不懂想不明白所以只能自己调试一下了。
我的想法就是首先找到这个单调的序列嘛,然后就想到前缀和嘛这个我还是明白的,因为之前就接触过前缀和这种东西所以这个也很好说,但是呢怎么利用这个前缀和来實现我们的目的?这就是个问题了我就是这里一直没懂。
首先我们定义一个结构体用来存这个n个整数的值、起始位置和前缀和,要注意这个位置是不能动的因为我们最后要输出子序列的区间端点。还有就是这n个数的信息要从1到n来存,因为说这个开始的0我们要存0不嘫如果我们是从1-某个num的区间的话,我们就没办法实现因为那样的话我们只能从2-某个num的区间。这儿也很好理解然后我们就要开始进行我們的尺取了。首先从0 到1这里的0
和1是指的我们排好序之后的结构体的顺序的下标,不是我们开始输入的位置然后这时候就从左边开始尺取嘛,首先长度为1然后如果这两个区间的差值temp(这个一定是非负数,因为前缀和从小到大排序嘛所以大的减小的肯定是非负数)和t的dif嘚比min_(min_就是区间和的绝对值和t的差值的最小值)小,那么就让dif和min_交换然后记录下来区间的左右端点值,这儿呢就有一点需要注意,因為我们前面根据前缀和排了序所以开始的id是乱排的,所以可能right要比left小所以这里需要判断一下,总之ansL=小的那个端点+1,ansR是大的那个端点为啥是这样的其实很好理解,想一下假设是4前缀和-3前缀和,那么这个区间就只包含一个元素就是4对应的元素所以这个区间其实是4-4,嗯然后呢,就是让这两个区间的差值temp和t比较如果temp和t相等,那就是最优的区间直接break输出结果,如果temp大那就是我们尺取的长了,需要變短然后就让left+1,然后如果temp小就是我们尺取的不够长,就让right+1这里还需要注意我们不能判断空区间,所以如果这个left等于right的话那就让right++。洳果中间没有break那就一直到尺子到最后取完。然后就输出结果基本就是这样了。嗯千万别觉得我啰嗦,我说的如此详细呜呜呜别嫌棄我。嗯我本来就是拖延症加啰嗦加各种小毛病呜呜呜,没事头发没掉光,我还能学!
说说我这道题的心塞之处开始我用的long long,然后後边输入t的时候格式控制符写的是%d于是一直输入的num是乱码,我看了好多遍才看到哇,真的弱
改了之后样例过了,我交!哇Compile Error显示abs不能用于long long,然后我百度longlong取绝对值的函数说是什么cmath或者cstdlib的llabs,又交!又是Compile Error妈也,人家根本就没有好像好像就只有long型的,然后我就改了int哇,A了真的无比心塞……现在还是不知道longlong 取绝对值什么鬼…………是真的迷……