P3594 [POI2015]WIL-Wilcze doły

题目描述

给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。

输入格式：

第一行包含三个整数n,p,d(1<=d<=n<=2000000，0<=p<=10^16)。第二行包含n个正整数，依次表示序列中每个数wi。

---

调试日志： 开始 p 和 d 输反了。。。查了半天、、老想自己哪里想错了QAQ

---

Solution

首先感性认识一下， 随着某一特定的右端点的增加， 其对应的最优左端点是会增加的

也就是说左端点随着右端点的单调递增

贪心认识一下， 由于元素大小大于0， 消去的能选满一定选满

所以处理出 \(maxx[i]\) 表示以 \(i\) 作为起点， （在不越界的情况下）选满的值

因为左端点随右端点单调递增

我们枚举每一个右端点， 同时单调队列处理出现区间内的最大能消去值 \(M\)

若是仍 \(sum[i] - sum[now - 1] - M > p\) 那么只好更新左端点了

每次更新 \(ans\) 即可

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define REP(i, x, y) for(LL i = (x);i <= (y);i++)using namespace std;LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const LL maxn = 4000019;LL num, d, p;LL a[maxn];LL maxx[maxn];//以i开头的满长消去值LL sum[maxn];void init(){ num = RD(), p = RD(), d = RD(); REP(i, 1, num)a[i] = RD(), sum[i] = sum[i - 1] + a[i]; REP(i, 1, num){ LL now = i + d - 1 > num ? sum[num] : sum[i + d - 1]; maxx[i] = now - sum[i - 1]; } }struct Que{ LL val, Index; }Q[maxn];//存maxxLL head = 1, tail = 0;void push_back(LL v, LL i){ while(head <= tail && Q[tail].val <= v)tail--; Q[++tail] = (Que){v, i}; }LL now;//目前真实队列的队头LL get_max(){ while(head <= tail && Q[head].Index < now)head++; return Q[head].val; }LL ans;void solve(){ now = 1; REP(i, d, num){ push_back(maxx[i - d + 1], i - d + 1); LL M = get_max(); while(sum[i] - sum[now - 1] - M > p)now++, M = get_max(); ans = max(ans, i - now + 1); } printf("%lld\n", ans); }int main(){ init(); solve(); return 0; }
         
        
       
      
     
    

CG