解题思路:
注意事项:
参考代码:
#include <cstdio> #include <cmath> #include <iostream> using namespace std; int n, m; int A[200001]; int size; int bmin[500]; void init(); void update(int x, int v); int query(int left, int right); int read(); int main() { char c; int a, b; scanf("%d %d", &n, &m); for (int i =0; i < n; ++i) A[i]=read(); size=(int)sqrt(n); init(); for (int i = 0; i < m; ++i) { a=read(); b=read(); printf("%d ", query(a-1, b-1)); } return 0; } int query(int left, int right) { int ret = 2147483647; int lstop=(left-1)/size; int rstop=(right+1)/size; for (int i = lstop+1; i < rstop; ++i) {ret=min(ret, bmin[i]);} for (int i = left; i < (lstop+1)*size&&i<=right; ++i) {ret=min(ret, A[i]);} for (int i = max((rstop-1)*size+1, left); i<=right; ++i) {ret=min(ret, A[i]);} return ret; } void init() { for (int i = 0; i <= size; ++i) bmin[i]=2147483647; int belong; for (int i = 0; i < n; ++i) { belong = i/size; bmin[belong]=min(bmin[belong], A[i]); } } int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f=-1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题7.2 (Java代码)浏览:681 |
矩阵乘法 (C++代码)浏览:1460 |
这可能是一个假的冒泡法浏览:985 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:655 |
C语言训练-尼科彻斯定理 (C语言代码)浏览:466 |
三角形 (C语言代码)浏览:910 |
蚂蚁感冒 (C语言代码)浏览:1330 |
1126题解浏览:585 |
上车人数 (C语言代码)浏览:711 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:502 |