HUNNU Contest 区间求最值 - c++编程基础

区间求最值

Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:32768KB

Total submit users: 68, Accepted users: 45

Problem 11460 : No special judgement

Problem description

给定一个长度为N 的数组，有q个询问，每个询问是求在数组的一段区间内那个元素的因子的个数最大，比如24的因子的个数就是8。

Input

首先是一个整数t，表示有t组测试数据，每组测试数据的第一行是一个整数N(1<=N<=10^6),第二行有N个整数a_i(1<=a_i<=10^6,i=1,2,.....N)表示数组的元素。第三行有一个整数q(1<=q<=10^5)，代表有q个询问，接下来每一行有两个整数，l_i,r_i(l_i<=r_i,l_i>=1,r_i<=N).代表数组的一段区间,并且l_i+1>=l_i,r_i+1>=r_i。

Output

对于每组数据的每个询问都输出一个整数表示在这段区间里面元素因子个数的最大值。

Sample Input

1
10
2 3 5 6 9 11 12 36 39 44
3
2 6
3 8
3 9

Sample Output

4
9
9

Problem Source

HUNNU Contest
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11460

这题感觉很巧妙，首先学到了怎么把给定范围因子数打表，然后怎么降低时间复杂度。

如果打表后每次直接在给定范围内比较出最大值是会超时的，但是我们可以把前一次比较出来的最大值下标赋值出来，下次查找的话，直接从这个下标开始，会节约很多时间。

#include 
      
       
#include 
       
         #define maxn 1000005 int find[maxn]; int num[maxn]; int main() { memset(find, 0, sizeof(find));//把 maxn范围内数的因子数打表 for (int i = 1; i < maxn; i++){ for (int j = i; j < maxn; j += i) //每次加i就等于j扩大一倍，两倍，三倍，，，，， find[j]++; } int t; scanf("%d", &t); while (t--) { int n, q; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &num[i]); //intf("%d\n",find[num[i]]); } scanf("%d", &q); int a, b, ans = -1; int aa, bb, sign; scanf("%d%d", &a, &b); aa = a, bb = b; for (int i = a; i <= b; i++) //先比较出第一组的最大值 保存下标 if (ans < find[num[i]]){ ans = find[num[i]]; sign = i; } printf("%d\n", ans); --q; //注意 while (q--) { scanf("%d%d", &a, &b); if (sign >= aa&&sign <= a){ //如果上一次的下标在aa和a之间，那只能从a开始 ans = -1; for (int i = a; i <= b; i++) if (ans < find[num[i]]){ ans = find[num[i]]; sign = i; } } else //否则直接从bb开始，因为else的话 sign只能是大于a。所以可以直接从bb开始。 { for (int i = bb; i <= b; i++) if (ans < find[num[i]]){ ans = find[num[i]]; sign = i; } } aa = a, bb = b; printf("%d\n", ans); } } return 0; }