本文主要是介绍PAT甲级-1044 Shopping in Mars，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
题目大意
一串项链上有n个钻石，输入给出每个钻石的价格。用m元买一个连续的项链子串（子串长度可为1），如果不能恰好花掉m元，就要找到最小的大于m的子串，如果有重复就输出多个，按递增顺序输出子串的前端和后端索引。
原来的思路
取连续的子串使和恰等于m，没有恰等于就找最小的大于。可以将子串依次累加，使得每个位置都是起始位置到该位置的序列和，整个数组显递增顺序，就可以用右边减左边的方式找到满足条件的子串。直接暴力for循环，这里我的数组从0开始，没有从1开始，所以又将满足条件的子串首端索引为0的情况单拎出来，很不推荐。其次还将等于m和大于m的情况拆开求解，设了个flag，如果前期有输出的话flag为1，没有输出flag为0时再考虑样例二。没有看成>=统一求解，也不推荐。所以就超时了。
原来的代码
#include <iostream>
#include <vector>
using namespace std;int main(){int n, money;cin >> n >> money;vector<int> v(n);for (int i = 0; i < (int)v.size(); i++){int num;cin >> num;i == 0 ? v[i] = num : v[i] = num + v[i - 1];} // 这个思路很重要int flag = 0;for (int i = 0; i < (int)v.size(); i++){if (v[i] == money){cout << "1-" << i + 1 << endl;flag = 1;}} // 查找从起始位置开始符合money的子串int maxi = 0;int q, h; // 记录前后i的位置for (int i = 0; i < (int)v.size(); i++){for (int j = i - 1; j >= 0; j--){if (v[i] - v[j] == money){cout << j + 2 << "-" << i + 1 << endl;flag = 1;}else if (v[i] - v[j] > money){if (maxi < v[i] - v[j]){maxi = v[i] - v[j];q = j + 2;h = i + 1;}break;}}}if (flag == 0){cout << q << "-" << h << endl;for (int i = h; i < (int)v.size(); i++){for (int j = i - 1; j >= 0; j--){if (v[i] - v[j] == maxi){cout << j + 2 << "-" << i + 1 << endl;}else if (v[i] - v[j] > maxi){break;}}}} //测试样例2return 0;
}思路
改进参考了柳神的代码。首先就是将数组容量改为n + 1，让钻石从1开始。之前我用了两个for循环，第一个遍历i，第二个遍历j，找满足v[j] - v[i] = m的值。数组是递增顺序，可以将第二个循环用二分法优化，即在给定区间找j。然后就是将等于m和大于m这两种情况合并成>=m，也即找到>=m的最小区间，定i找j，也就是找区间的最小右边界。这时就需要考虑结果的输出形式，不能边找边输出，只能用个数组存，如果有更小的边界值就清空数组重新放。
知识点
在二分查找中，如果要找某区间的最小边界，而不是具体的找某个值，while循环的条件就要设为low < high，如果要用二分查找找到某个值，条件就设为low <= high，此时循环最终范围缩小到1位。
如果要在函数中调用数组，要将该数组设成全局变量，如果设成局部变量不断引用，会占用大量堆栈空间，可能会超时。某个数的话设成局部变量还ok。
AC代码
#include <iostream>
#include <vector>
using namespace std;int n, money;
vector<int> v; // 不设成全局变量就会超时void find_j(int i, int &j, int &mint){int high = n;int low = i;while (low < high){ // 二分查找最小满足条件的边界，所以不加=号int mid = (low + high) / 2;if (v[mid] - v[i - 1] < money){low = mid + 1;}else{high = mid; // 这里保留mid，进一步缩小范围，因为mid也可能是最小索引}}j = high; // high值才是最终的二分查找结果mint = v[j] - v[i - 1];
} // 二分法找到满足条件的最小索引int main(){cin >> n >> money;v.resize(n + 1);for (int i = 1; i <= n; i++){int num;cin >> num;v[i] = num + v[i - 1];} // 累加使得数组呈递增int mini = v[n];vector<int> res;for (int i = 1; i <= n; i++){int j, mint; // i在前，j在后find_j(i, j, mint); // 使用二分查找找到最小满足条件的jif (mint <= mini && mint >= money){if (mint < mini){mini = mint;res.clear();}res.push_back(i);res.push_back(j);}}for (int i = 0; i < (int)res.size(); i += 2){cout << res[i] << "-" << res[i + 1] << endl;}return 0;
}
这篇关于PAT甲级-1044 Shopping in Mars的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
