题目大意

给你一串二元组\((a_i,b_i)\)的数列。

求最小的区间\([l,r]\)长度，满足\([l,r]\)中的每个二元组选或不选，使得\(\sum a_i=w\)且\(\sum b_i\leq k\)

思考历程

想了好久，想来想去都是一个背包……

最终决定打暴力……

正解

先说说GMH大爷的神奇解法。

首先是二分答案\(ans\)，转化成判定问题。然后在数列中每\(ans\)个点设置一个观测点。

以每个观测点为中心，向左和向右背包，然后合并。

然而正解并不需要一个\(\log\)

考虑双指针，就是记一个当前的最佳答案\(ans\)，后面的区间长度都要小于\(ans\)。脑补一下这个过程，其实这就是一个队列，只需要支持左边出右边入的队列。

但是背包问题不满足可减性。于是就有个非常骚的解法：

把这个队列用两个栈来代替，栈顶分别为队头和队尾。

加入的时候，就在第二个栈的栈顶加入；弹出的时候，就直接弹出第一个栈的栈顶。

如果第一个栈为空，那就将第二个栈里的东西倒过来放到第一个栈中，然后暴力重构。

每个元素只会暴力重构一次，所以不会时间超限。

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 10010#define maxW 5010inline int input(){    char ch=getchar();    while (ch<'0' || '9'
        
         b?a=b:0;}inline bool ok(int j){    int jj=st1[top1];    for (int k=0;k<=W;++k)        if (f[jj][k]+f[j][W-k]<=K)            return 1;    return 0;}int main(){    freopen("cactus.in","r",stdin);    freopen("cactus.out","w",stdout);    n=input(),W=input(),K=input();    for (int i=1;i<=n;++i)        a[i]=input(),b[i]=input();    int ans=n+1;    f[0][0]=0;    for (int i=1;i<=W;++i)        f[0][i]=K+1;    for (int i=1,j=1;i<=n;++i){        if (ok(st2[top2]))            ans=j-i;        for (;j<=n && j-i+1
         
          =1;--j) st1[++top1]=st2[j]; top2=0; for (int j=1;j