程序员进阶之算法练习（三）
前言
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目链接 题目大意：n个数字，找出连续一串上升序列的长度。 代码实现：
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个数字，寻找a[i] + a[j] = 2^x，并且i < j。算出总共有多少对存在？
方法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个目标点，m个源点，求最小的r，使得每个目标点的r范围内至少存在一个源点。 代码实现：
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可行，那么r+1必然可行。可以用二分。 同时，目标点i对应的源点为j，那么有i+1目标点的源点>=j。
D
题目链接 题目大意：从起点到终点的距离为d，骑车速度为a秒/公里，走路速度为b秒/公里(a < b)。车子每走k公里就要修理一次，时间为t秒。车子最初k公里不需要修理，问最短的时间到达终点。 代码实现：
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公里必然也是骑车。