1082 - Array Queries PDF (English) Statistics ForumTime Limit: 3 second(s) Memory Limit: 64 MBGiven an array with N elements, indexed from 1 to N. Now you will be given some queries in the form I J, your task is to find the minimum value from index I to J.
InputInput starts with an integer T (≤ 5), denoting the number of test cases.
The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 105), q (1 ≤ q ≤ 50000). The next line contains N space separated integers forming the array. There integers range in [0, 105].
The next q lines will contain a query which is in the form I J (1 ≤ I ≤ J ≤ N).
OutputFor each test case, print the case number in a single line. Then for each query you have to print a line containing the minimum value between index I and J.
Sample InputOutput for Sample Input25 378 1 22 12 31 23 54 41 1101 1Case 1:1312Case 2:10
思路: 可用线段树， 但用分块来求，容易写，也不容易出现错误。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 100100,inf = 1000000; int a[N]; int size[N/2]; int main(){ int T,n,q,under1,under2,m,uu1,uu2,minn; scanf("%d",&T); for(int t=1;t<=T;t++){ memset(size,10,sizeof(size)); scanf("%d%d",&n,&q); m = sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); size[(int)i/m] = min(size[(int)i/m],a[i]); } printf("Case %d:\n",t); for(int i=0;i<q;i++){ scanf("%d%d",&under1,&under2); uu1 = (int)under1/m; uu2 = (int)under2/m; minn = inf; for(int j = under1;j<=min((uu1+1)*m-1,under2);j++){ minn = min(minn,a[j]); } for(int j = uu1+1;j<uu2;j++){ minn = min(minn,size[j]); } if(uu1!=uu2){ for(int j=uu2*m;j<=under2;j++) minn = min(minn,a[j]); } printf("%d\n",minn); } } return 0; } View Code
转载于:https://www.cnblogs.com/yuanshixingdan/p/5539991.html
