好印象深刻的题，前天选拔赛给跪了。怪我这种关键题没敲出来。
题意很简单，给你一串无规则的数列，再给个m值，求出满足 数列和>=m的长度最小的连续子串。。。确实一开始卡住了，因为看数据肯定是nlogn的算法才能过，我和聪哥坐在外面的楼梯上，想了各种方法，我就一直在想前缀和以及 先求出最长连续和 再两边删减等等，刚提出来 就马上否定了。。后来还是聪哥想出个比较靠谱的方案，即二分结果，然后对二分出来的结果 先枚举右端点，再通过二分的结果得到左端点，找到左端点和右端点中间最小的前缀和，用左端点的前缀和 减去 最小的前缀和，如果结果>=m,意味着该二分结果可行，可以继续缩小下去，否则说明不行。
然后我就敲了，结果一直WA，后来知道自己哪里傻逼了，我对二分出来的len，在枚举右端点的时候，直接就是从len到n，0-(len-1)这里就没有枚举右端点，事实是，可能恰好结果就在0-(len-1），真是傻逼
不过这个算法确实是正确的，但还是有时限问题 因为多了个二分，其时间复杂度就变成了 n*logn*logn,所以只好聪哥改了我上面的漏洞之后，果然A了，不过用了1.7s，而且，之后我再提及他的同样的代码，就TLE了，估计是UVA的机器突然又跑慢了。所以这个算法还是有问题的。
后来跟聪哥讨论后觉得二分可能可以去掉不要，确实可以去掉。。。我又傻逼了，这么简单问题没想到，预处理完suffix前缀和之后，题目不就是要求suffix[右端点]-suffix[i]>=m，满足这个条件的 离右端点的最近的点，也就是说 我令 val=suffix[i]<=suffix[右端点]-m，即求离右端点最近的满足>=val的suffix所在的点，如果我线段树里面维护的是suffix的最小值，那么我为了求离右端点最近的，我肯定是对 线段树这样query：假如当前右子树满足 >=val,则优先走右子树，否则如何左子树>=val,则走左子树，如果左右都走不了 就是-1了
这样得到的值必定是离右端点最近的啊啊啊啊。
我真是傻逼
这是之前的思路 算法正确 但是会TLE
#include <iostream> #include <cstdio> #define N 500010 #define LL long long #define lson rt<<1,l,mid #define rson (rt<<1|1),mid+1,r using namespace std; LL suffix[N]; int n,m; LL tree[N*3]; void build(int rt,int l,int r) { if (l>=r){ tree[rt]=suffix[l]; return; } int mid=(l+r)>>1; build(lson); build(rson); if (tree[rt<<1]>tree[rt<<1|1]) tree[rt]=tree[rt<<1|1]; else tree[rt]=tree[rt<<1]; } LL query(int L,int R,int rt,int l,int r) { if (L<=l && r<=R){ return tree[rt]; } int mid=(l+r)>>1; if (R<=mid){ return query(L,R,lson); } if (L>mid){ return query(L,R,rson); } return min(query(L,R,lson),query(L,R,rson)); } int ok(int x) { for (int i=2;i<=n;i++){ //这里应该从前面开始枚举，比赛的时候就是直接从len开始枚举，导致一直WA。。。虽然改了也不一定会避免时限超时，但总归这样是我敲错了，那样是我们思路错了，性质不一样。 int j=i-x; if (j<0) j=0; LL mini; if (i==2) mini=0; else mini=query(j,i-2,1,0,n); if (suffix[i]-mini>=m) return 1; } return 0; } int main() { int t; scanf("%d",&t); while (t--){ suffix[0]=0; scanf("%d%d",&n,&m); bool isok=0; for (int i=1;i<=n;i++){ scanf("%lld",&num[i]); suffix[i]=suffix[i-1]+num[i]; if (num[i]>=m) isok=1; } if (isok){ puts("1"); continue; } if (m<=0){ puts("-1"); continue; } build(1,0,n); int L=2,R=n+1,mid; bool flag=0; int ans=-1; while (L<R) { mid=(L+R)>>1; if (ok(mid)){ flag=1; ans=mid; R=mid; } else L=mid+1; } if (!flag){ puts("-1"); } else printf("%d ",ans); } return 0; } /* 7 7 3 -2 1 6 1 -2 3 */
AC代码
#include <iostream> #include <cstdio> #include <cstring> #define N 500010 #define LL long long #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r using namespace std; LL suffix[N]; int n,m; LL tree[N*3]; void build(int rt,int l,int r) { if (l>=r){ tree[rt]=suffix[l]; return; } int mid=(l+r)>>1; build(lson); build(rson); if (tree[rt<<1]>tree[rt<<1|1]) tree[rt]=tree[rt<<1|1]; else tree[rt]=tree[rt<<1]; } int query(LL val,int L,int R,int rt,int l,int r) { if (l>=r) return l; int mid=(l+r)>>1; int ret1=-1,ret2=-1; if (mid<R) //因为是从顶点开始搜索起的，所以用L和R来控制区间 if(val>=tree[rt<<1|1]){ //优先找右子树，就能得到最近的点 ret1=query(val,L,R,rson); } if (L<=mid) if (val>=tree[rt<<1]){ ret2=query(val,L,R,lson); } int ret=max(ret1,ret2); return ret; } int main() { int t; scanf("%d",&t); while (t--){ suffix[0]=0; scanf("%d%d",&n,&m); bool isok=0; for (int i=1;i<=n;i++){ scanf("%lld",&suffix[i]); if (suffix[i]>=m) isok=1; suffix[i]+=suffix[i-1]; } if (isok){ puts("1"); continue; } if (m<=0){ puts("-1"); continue; } build(1,0,n); int ans=N; for (int i=2;i<=n;i++){ LL v=suffix[i]-m; int res=query(v,0,i-1,1,0,n); //对每个v 在 0到 i-1的区间里，从线段树的顶点开始搜索起，得到离右端点最近的点。 if (res!=-1) ans=min(ans,i-res); // cout<<i<<" "<<res<<endl; } if (ans==N) ans=-1; printf("%d ",ans); } return 0; }