5 1-10 -5 0 5 10310 2-9 8 -7 6 -5 4 -3 2 -1 05 1115 2-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -115 1000 0
5 4 45 2 89 1 115 1 1515 1 15
这道题,ennn卡了我好久,一直不知道怎么去尺取。。。。。。
其实,对于每一段(a, b](特别注意是前开后闭区间),我们都可以把这一段的和看成从第一个加到第b个减去从第一个加到第a个的差,这样我们就能计算了。
自于尺取的话,我们应当在判断每种情况下区间与t的差值,如果差值小,我们就更新,首先我们对所有的和进行排序。
至于怎么取,我们可以分以下几种情况:
1.从一开始判断,一开始就取第一个,左边界是0(因为前开后闭),右边界是1,如果第一个的值小于t,我们也可以取第二个(即右边界 ),一直这样。
2.当进行情况1时出现取的区间和大于t时(假设此时区间为(0,a]),继续增大和将使得与t的差值肯定大于此时的差值(我们都知道,如果和是单调递增的,那么区间的值会先向t逼近,然后又远离t,因为t大于等于0,而和又一直上涨,所以与t的差值是先减小,后增大),所以出现了右边界减去左边界大于t时,之后右边界 后的和与t的差值肯定大于当前,所以没有必要继续下去。
接下来怎么办,我们考虑移动左边界,那右边界要不要发生变化呢?如果从第二个开始(即从(1,2]开始),又依次循环到比t大的,时间复杂度很高,尺取的优势就在这里了:在右边界小于a(我们假设右边界为b(b < a)),左边界大于0的情况下都是在(0,b]包含内的,而b < a,则(0, b]因为b < a而(0, a]才是第一次大于t,所以(0,b]<t,故有(1,b] < (0, b] < t,所以(0, b]与t的差值小于(1,b]与t的差值,所以当左边界向右移动的时候,右边界如果小于a都不可能出现差值比之前小的值,我们也就不用去搜索,但是(1,a]我们并不知道是否大于t,所以我们还是得判断,同样如果小于t,还是按照情况1的方法。
3.特别情况,因为是前开后闭区间,所以左边界不能等于右边界,这样的值是不存在的,当t==0时,如果放任这种情况就会更新最小的差值就会出错,我们应当把它转变成下一种情况,也就是右边界 。
4.对于当最小差值为0时,没有必要继续判定了,直接break;
至于排序,我们直接按照从第一个加到第n个的和的顺序进行排序,这样可以使得每次右边界 时和都会大于先前的,才能使得序列具有单调性,而单调性不能少,如果少了就不能正确得出答案。特别的不要忘记排序的时候前0个也要带上,因为真正的左区间可能取第0个也就是从1开始算起,至于排序可能造成的左区间大于右区间的情况,我们结果只要对调一下就好了,值还是不变的,详见代码。
归纳一下:
1.如果区间和小于t,则右边界 ;
2.如果区间和大于t,则左边界 ;
3.如果区间和等于t,直接break;
4.如果左右边界相同,右边界 ;
AC代码:
#include <stdio.h>#include <algorithm>using namespace std;long long abst(long long a)//abs好像不支持long long,不过好像说这道题int也能过{ return a >= 0? a:-a;}typedef long long ll;const ll INF = 0x3fffffffffffffff;ll a[100005];//记录原始序列,但是好像没有必要,直接一个变量就好了struct Node { ll sum;//1到i的和 ll i;}sum[100005];ll q;//询问的值ll min_s, min_e;//最小的起始末尾bool cmp(Node x, Node y){ if(x.sum == y.sum) return x.i < y.i; return x.sum < y.sum;}int main(void){ ll n, k; while(scanf("%lld %lld",&n, &k) && n k) { sum[0].sum = sum[0].i = 0;//一定要注意每次排完序sum第一个值不一定都是0 for(ll i = 1; i <= n; i ) { scanf("%lld", &a[i]); sum[i].sum = sum[i - 1].sum a[i]; sum[i].i = i; } sort(sum , sum n 1, cmp);//记得排序带上sum【0】,代表着从第0个作为开区间也就是从第一个算起,因为是前开区间,所以left的范围是【0,n - 1】,right的范围是【1,n】 for(ll i = 0; i < k; i ) { scanf("%lld", &q); ll min_cut = INF;//与t最小差值 ll value;//区间值 ll left = 0, right = 1;//左右边界,前开后闭 while(right <= n) { if(abst(abst(sum[right].sum - sum[left].sum) - q) <= min_cut) { min_cut = abst(abst(sum[right].sum - sum[left].sum) - q);//更新最小差值 min_s = sum[left].i; min_e = sum[right].i; value = abst(sum[right].sum - sum[left].sum); } if(abst(sum[right].sum - sum[left].sum) - q > 0) left ; else if(abst(sum[right].sum - sum[left].sum) - q < 0) right ; else break; if(left == right) right ; } if(min_s > min_e)//因为排序可能造成left的i大于right的i,这个没关系,这样的值还是存在的,只不过前开区间就是min_e罢了,直接交换就好了 swap(min_s, min_e); printf("%lld %lld %lld\n", value, min_s 1, min_e);//注意因为是前开后闭,前开不能忘记 1 } } return 0;}
来源:https://www.icode9.com/content-1-647401.html
联系客服