2.
#include <iostream>
using namespace std;
const int N = 1001;
int n, a[N];
int ans = 0;
void dfs(int L, int R) {
if(L > R)
return;
int p = L;
for(int i = L + 1; i <= R; i += 1)
if(a[i] < a[p])
p = i;
ans += (p - L + 1) * (R - p + 1) * a[p];
dfs(L, p - 1);
dfs(p + 1, R);
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i += 1)
cin >> a[i];
dfs(1, n);
cout << ans << endl;
}
判断题
1) 如果输入n = 1000, 所有的a[i] = 100000，程序不会产生整形溢出。（ ）
2) 将第11行改为if(L >= R) 程序仍然可以计算出相同的结果。（ ）
3) 当n = 4, a = {1, 2, 4, 3}时，输出为20。（ ）
选择题
4) 该程序的最劣复杂度为（ ）。
5) 该程序在a为1,2,…,n的随机排列时，时间复杂度的期望为（ ）。
3.
#include <iostream>
using namespace std;
const int N = 100001;
int n, a[N];
int check(int a, int b, int c) {
return (a <= c && c <= b) || (b <= c && c <= a);
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i += 1) {
cin >> a[i];
a[i] += a[i - 1];
}
int q;
cin >> q;
while(q--) {
int L, R;
cin >> L >> R;
int target = (a[L] + a[R]) / 2;
int pos = -1;
while(L != R) {
int mid = (L + R) / 2;
if(a[mid] == target) {
pos = mid;
break;
}
if(check(a[L], a[mid - 1], target))
R = mid - 1;
else
L = mid + 1;
}
if(pos == -1)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
}
判断题
1) 该算法的时间复杂度为Θ((n+q)*log(n))。（ ）
2) 程序输出NO时，代表不存在l<=x<=r，使得a[x]=target。（ ）。
选择题
3) 当输入的n = 3，输入的a[i]分别为2,3,1, q=2, 两组询问分别为L=2,R=3和L=1,R=3时，输出的是（ ）。
4) 当输入的n = 100，输入的a[i]当i为奇数时为-1，偶数时为1, q=2, 两组询问分别为L=1,R=100和L=30,R=40时，输出的是（ ）。
5) 当a满足以下哪种条件时，程序总是输出YES（ ）。