很显然n方的复杂度过不了。
于是考虑优化最值的查询，可以考虑用堆或者单调队列来做。
堆：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 7 const int INF = 99999999; 8 const int N = 32768; 9 int a[N]; 10 int n, l, u; 11 12 struct Node 13 { 14 int l; 15 int s; 16 Node () {} 17 Node ( int _l, int _s ) 18 { 19 l = _l; 20 s = _s; 21 } 22 bool operator < ( const Node & t ) const 23 { 24 return s < t.s; 25 } 26 }; 27 28 int solve() 29 { 30 priority_queue<Node> q; 31 int ans = INF; 32 for ( int i = l; i <= n; i++ ) 33 { 34 q.push( Node ( i - l, a[i - l] ) ); 35 while ( q.top().l + u < i ) q.pop(); 36 int tmp = a[i] - q.top().s; 37 if ( tmp < ans ) ans = tmp; 38 } 39 return ans; 40 } 41 42 int main() 43 { 44 while ( scanf("%d", &n), n ) 45 { 46 scanf("%d%d", &l, &u); 47 a[0] = 0; 48 for ( int i = 1; i <= n; i++ ) 49 { 50 scanf("%d", a + i); 51 a[i] += a[i - 1]; 52 } 53 printf("%d ", solve()); 54 } 55 return 0; 56 }
单调队列：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 7 const int INF = 99999999; 8 const int N = 32768; 9 int a[N]; 10 int n, l, u; 11 int head, tail; 12 13 struct Node 14 { 15 int l, s; 16 } q[N]; 17 18 int solve() 19 { 20 int ans = INF; 21 head = tail = 0; 22 for ( int i = l; i <= n; i++ ) 23 { 24 while ( head < tail && a[i - l] > q[tail - 1].s ) 25 { 26 tail--; 27 } 28 q[tail].l = i - l, q[tail].s = a[i - l]; 29 tail++; 30 while ( q[head].l + u < i ) head++; 31 int tmp = a[i] - q[head].s; 32 if ( tmp < ans ) ans = tmp; 33 } 34 return ans; 35 } 36 37 int main() 38 { 39 while ( scanf("%d", &n), n ) 40 { 41 scanf("%d%d", &l, &u); 42 a[0] = 0; 43 for ( int i = 1; i <= n; i++ ) 44 { 45 scanf("%d", a + i); 46 a[i] += a[i - 1]; 47 } 48 printf("%d ", solve()); 49 } 50 return 0; 51 }
块状链表：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 using namespace std; 6 7 const int INF = 999999999; 8 const int N = 32768; 9 const int M = 500; 10 int a[N]; 11 int n, tot; 12 int ps; 13 int lower, upper; 14 15 int max( int a, int b ) 16 { 17 return a > b ? a : b; 18 } 19 20 int min( int a, int b ) 21 { 22 return a < b ? a : b; 23 } 24 25 struct Block 26 { 27 int num[M]; 28 int size, maxn; 29 void init() 30 { 31 size = 0; 32 maxn = -INF; 33 } 34 void push( int tmp ) 35 { 36 num[size++] = tmp; 37 if ( tmp > maxn ) maxn = tmp; 38 } 39 } bl[M]; 40 41 int query( int l, int r ) 42 { 43 l++, r++; 44 int cur = 0, ncur = 0; 45 while ( l > ps ) 46 { 47 l -= ps; 48 cur++; 49 } 50 while ( r > ps ) 51 { 52 r -= ps; 53 ncur++; 54 } 55 int ans = -INF; 56 for ( int i = cur + 1; i <= ncur - 1; i++ ) 57 { 58 ans = max( ans, bl[i].maxn ); 59 } 60 if ( cur == ncur ) 61 { 62 for ( int j = l - 1; j < r; j++ ) 63 { 64 ans = max( ans, bl[cur].num[j] ); 65 } 66 } 67 else 68 { 69 for ( int j = l - 1; j < bl[cur].size; j++ ) 70 { 71 ans = max( ans, bl[cur].num[j] ); 72 } 73 for ( int j = 0; j < r; j++ ) 74 { 75 ans = max( ans, bl[ncur].num[j] ); 76 } 77 } 78 return ans; 79 } 80 81 int main() 82 { 83 while ( scanf("%d", &n), n ) 84 { 85 scanf("%d%d", &lower, &upper); 86 a[0] = 0; 87 for ( int i = 1; i <= n; i++ ) 88 { 89 scanf("%d", a + i); 90 a[i] += a[i - 1]; 91 } 92 tot = 0; 93 bl[tot].init(); 94 ps = sqrt((double)n); 95 for ( int i = 0; i <= n; i++ ) 96 { 97 if ( bl[tot].size == ps ) 98 { 99 tot++; 100 bl[tot].init(); 101 } 102 bl[tot].push(a[i]); 103 } 104 int ans = INF; 105 for ( int i = lower; i <= n; i++ ) 106 { 107 int qq = query( max( i - upper, 0 ), i - lower ); 108 ans = min( ans, a[i] - qq ); 109 } 110 printf("%d ", ans); 111 } 112 return 0; 113 }
还可以用线段树或者RMQ的ST算法，解法实在是太多了。