首页 > 代码库 > BZOJ 2086: [Poi2010]Blocks
BZOJ 2086: [Poi2010]Blocks
2086: [Poi2010]Blocks
Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 494 Solved: 222
[Submit][Status][Discuss]
Description
给出N个正整数a[1..N],再给出一个正整数k,现在可以进行如下操作:每次选择一个大于k的正整数a[i],将a[i]减去1,选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后,问最大能够选出多长的一个连续子序列,使得这个子序列的每个数都不小于k。
总共给出M次询问,每次询问给出的k不同,你需要分别回答。
Input
第一行两个正整数N (N <= 1,000,000)和M (M <= 50)。
第二行N个正整数,第i个正整数表示a[i] (a[i] <= 10^9)。
第三行M个正整数,第i个正整数表示第i次询问的k (k <= 10^9)。
Output
共一行,输出M个正整数,第i个数表示第i次询问的答案。
Sample Input
1 2 1 1 5
1 2 3 4 5 6
Sample Output
HINT
Source
分析
题意可以简化为选取最长的一段,使得其平均值不小于k。
问题又可以进一步转化为将原序列的每个数减k,然后找最长的一段使得其和不小于0。
设转换后的新序列为seq,sum为seq的前缀和,则就是找一对i,j使得i<j且sum[i]<=sum[j],且j-i最大。
观察发现,对于seq中的位置i,如果存在j<i且sum[j]<=sum[i],则i不会用来更新最优解,因为无论如何j都比它优。所以可以先求出seq中单调下降的子序列(可能不连续),存入一个栈里。
for (int i = 1; i <= n; ++i) if (sum[i] > sum[stk[tot]]) stk[++tot] = i;
又发现,对于这个单调下降序列中的一个元素,其都可以作为我们的i,如果我们倒序枚举j,则一个i被某个j用来更新之后就不会再用来更新了,因为那个j一定使得sum[i]<=sum[j]的最大的j了。所以每个i更新完就出栈,保证时间复杂度是O(N)的。
后记:不知道写的时候满脑子在想什么,都没发现前缀和会爆int,后来感觉自己真是没救了,退役保平安吧……
代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 1000005; 7 8 int n, m, k; 9 int num[N]; 10 int seq[N]; 11 int stk[N]; 12 LL sum[N]; 13 14 signed main(void) 15 { 16 scanf("%d%d", &n, &m); 17 for (int i = 1; i <= n; ++i) 18 scanf("%d", num + i); 19 while (m--) 20 { 21 scanf("%d", &k); 22 for (int i = 1; i <= n; ++i) 23 seq[i] = num[i] - k; 24 for (int i = 1; i <= n; ++i) 25 sum[i] = sum[i - 1] + seq[i]; 26 int ans = 0, tot = 0; 27 for (int i = 1; i <= n; ++i) 28 if (sum[i] < sum[stk[tot]]) 29 stk[++tot] = i; 30 for (int i = n; i >= 1; --i) 31 while (~tot && sum[i] >= sum[stk[tot]]) 32 ans = max(ans, i - stk[tot--]); 33 printf("%d%c", ans, m ? ‘ ‘ : ‘\n‘); 34 } 35 }
@Author: YouSiki
BZOJ 2086: [Poi2010]Blocks