程序员进阶之算法练习（三）
前言
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目链接
题目大意：n个数字a[i]，从中找出最长连续上升子序列的长度。
a1, a2, ..., an (1 ≤ a[i] ≤ 1e9)
n (1 ≤ n ≤ 1e5)
Examples
input
5
1 7 2 11 15
output
3
代码实现：
int maxNum = 1, k = 1;
for (int i = 1; i < n; ++i) {
if (a[i] > a[i - 1]) {
++k;
maxNum = max(maxNum, k);
}
else {
k = 1;
}
}
题目解析：
对于一串序列，假如是以a[i]结尾，如果a[i+1] > a[i] 那么a[i+1]会让序列+1；如果a[i+1] <= a[i] 那么a[i+1]会重新开始新的序列。
B
题目链接
题目大意：给出n个数字 a1, a2, ..., an，寻找a[i] + a[j] = 2^x，并且i < j（x为任意数字）。算出总共有多少对存在？
n (1 ≤ n ≤ 1e5)
a1, a2, ..., an (1 ≤ ai ≤ 1e9).
Examples
input
4
7 3 2 1
output
2
方法1
代码实现：
for (int i = 0; i < n; ++i) {
long long k = 1;
while (k <= a[i]) {
k = k << 1;
}
k -= a[i];
long long left = 0, right = i - 1;
long long l = left, r = right;
while (left < right) { // 寻找 == k的左边界
// printf("%d %d %d \n", i, left, right);
long long mid = (left + right) / 2;
if (a[mid] > k) {
right = mid - 1;
}
else if (a[mid] < k) {
left = mid + 1;
}
else {
l = mid;
right = mid;
}
}
// printf("%d %d %d \n ------ \n", i, left, right);
if (a[left] == k) {
l = left;
}
left = 0;
right = i - 1;
while (left < right) { //选择 == k的右边界
// printf("%d %d %d \n", i, left, right);
long long mid = (left + right) / 2;
if (a[mid] > k) {
right = mid - 1;
}
else if (a[mid] < k) {
left = mid + 1;
}
else {
r = mid;
left = mid + 1;
}
}
// printf("%d %d %d \n", i, left, right);
if (a[right] == k) {
r = right;
}
if (a[l] == k && a[r] == k && r >= l) {
count += r - l + 1;
// if (a[l] == a[i]) {
// --count; // 排除自己
// }
}
题目解析：
对数组进行从小到大排序，假设有a[i] + a[j] = 2 ^x，并且i < j，x为大于a[j]的最小的2的幂。
那么在[1, j - 1]的区间内，不存在a[i] + a[j] = 2 ^ (x - 1)和 a[i] + a[j] = 2 ^ (x + 1)。
故而排序后，对于a[j]，只要求出值为(2^x - a[j])的区间即可。用二分查找。
方法2
代码实现：
#include <map>
map<int,int> M;
long long ans=0;
int main(){
int n,a;
cin>>n;
while(n--){
cin>>a;
for(int i=0;i<=31;i++) ans+=M[(1LL<<i) - a];
M[a]++;
}
cout<<ans;
}
题目解析：
对于每个数，只考虑前面的组合。
已知，最大数字不会超过2^31，那么对于每个数字枚举一遍即可，用map来存之前出现的数字。
C
题目链接
题目大意：
一维坐标轴上有n个目标点a[i]，m个源点b[i]，求最小的距离r，使得每个目标点的r范围内至少存在一个源点。
n and m (1 ≤ n, m ≤ 1e5)
输入数据：n、m，然后是a[i]，b[i]。( - 109 ≤ a[i], b[i] ≤ 109)
Examples
input
3 2
-2 2 4
-3 0
output
4
代码实现：
long long ret = (long long)2 * 10E9;
long long left = 0, right = ret;
while (left < right) {
long long mid = (left + right) / 2;
int j = 0;
for (int i = 0; i < n; ++i) {
while (j < m) {
if (a[i] >= b[j] - mid && a[i] <= b[j] + mid) {
break;
}
++j;
}
}
if (j < m) {
ret = mid;
right = mid;
}
else {
left = mid + 1;
}
}
题目解析：
如果r可行，那么r+1必然可行，符合二分要求。
同时，为了枚举更加迅速，可以先对a[i]和b[i]进行排序。对于每一个目标点i，我们从小开始选b[j]，值得出现一个符合要求；那么当目标点i对应的源点为j，那么有i+1目标点的源点>=j。
D
题目链接
题目大意：
小明要从家里去邮局，已知起点到终点的距离为d。
小明有一辆自行车，骑车速度为a秒/公里；他也可以走路，走路速度为b秒/公里(a < b)。
但是车子很旧，每走k公里就要修理一次，时间为t秒。（如果不修就要推着车子，速度和走路是一样）
车子最初k公里不需要修理，问最短的时间到达终点。
d, k, a, b, t (1 ≤ d ≤ 1e12; 1 ≤ k, a, b, t ≤ 1e6; a < b)
Examples
input
5 2 1 4 10
output
14
代码实现：
long long d, k, a, b, t;
cin >> d >> k >> a >> b >> t;
if (d <= k) {
ret = d * a;
}
else {
d -= k;
ret = a * k;
long long left = d % k;
long long c = d / k;
ret += min(k * a + t, k * b) * c;
ret += min(t + left * a, left * b);
}
题目解析：
先让车子走k公里（因为a<b)，接下来把剩下的路分成若干段，每段k公里，最后剩下的部分为left公里。
对于每段的k公里，根据k * a + t 和 k * b 的大小决定走路还是骑车；
最后的left公里，根据t + left * a 和 left * b的大小决定走路还是骑车；
是否存在前面走路，后面骑车的情况？
假设最后一段是骑车，那么前面的k公里必然也是骑车。
总结
题目不难，需要一点点思维能力。
