4385: [POI2015]Wilcze doły
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 648 Solved: 263[][][]Description
给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。
请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。Input
第一行包含三个整数n,p,d(1<=d<=n<=2000000，0<=p<=10^16)。
第二行包含n个正整数，依次表示序列中每个数w[i](1<=w[i]<=10^9)。Output
包含一行一个正整数，即修改后能找到的最长的符合条件的区间的长度。
Sample Input
9 7 2 3 4 1 9 4 1 7 1 3
Sample Output
5
HINT
将第4个和第5个数修改为0，然后可以选出区间[2,6]，总和为4+1+0+0+1=6。
Source
分析
显然单调队列O(N)扫过去即可，就是注意优化常数。
代码
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 #define gc getchar10 #define add(x,y) x=x*10+y-'0'11 12 template 13 __inline void read(T &x)14 {15 x = 0; char c = gc();16 17 while (c < '0')18 c = gc();19 20 while (c >= '0')add(x,c),21 c = gc();22 }23 24 #define mem(x) memset(x,0,sizeof(x))25 #define rep(x) for(int i=1;i<=x;++i)26 27 #define ll long long28 #define LL long long29 30 #define N 400000531 32 int n;33 int d;34 int num[N];35 int que[N];36 37 LL p;38 LL sum[N];39 LL mex[N];40 41 signed main(void)42 {43 read(n);44 read(p);45 read(d);46 47 rep(n)read(num[i]);48 rep(n)sum[i] = sum[i - 1] + num[i];49 rep(n - d + 1)mex[i] = sum[i + d - 1] - sum[i - 1];50 51 int h = 0, t = 0, lt = 0, ans = 0;52 53 for (int i = d; i <= n; ++i)54 {55 while (h < t && mex[que[t - 1]] <= mex[i - d + 1])56 --t;57 58 que[t++] = i - d + 1;59 60 while (sum[i] - sum[lt] - mex[que[h]] > p)61 {62 ++lt; while (que[h] <= lt)++h;63 }64 65 if (i - lt > ans)ans = i - lt;66 }67 68 printf("%d\n", ans);69 }
1 #include2 3 typedef long long longint; 4 5 const int maxn = 4000005; 6 7 int n; 8 int d; 9 int num[maxn];10 int que[maxn];11 12 longint p;13 longint sum[maxn];14 longint mex[maxn];15 16 signed main(void)17 {18 scanf("%d%lld%d", &n, &p, &d);19 20 for (int i = 1; i <= n; ++i)21 scanf("%d", num + i);22 23 for (int i = 1; i <= n; ++i)24 sum[i] = sum[i - 1] + num[i];25 26 for (int i = 1; i <= n - d + 1; ++i)27 mex[i] = sum[i + d - 1] - sum[i - 1];28 29 int head = 0, tail = 0, left = 0, answer = 0;30 31 for (int i = d; i <= n; ++i) {32 while (head < tail && mex[que[tail - 1]] <= mex[i - d + 1])33 --tail; // queue pop back34 35 que[tail++] = i - d + 1;36 37 while (sum[i] - sum[left] - mex[que[head]] > p) {38 ++left;39 while (que[head] <= left)40 ++head; // queue pop front41 }42 43 if (answer < i - left)44 answer = i - left;45 }46 47 printf("%d\n", answer);48 }
@Author: YouSiki