本文主要是介绍PAT1044. Shopping in Mars (25)(二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出一系列数字，要求输出子序列使其和等于m，如果没有等于m的子序列就输出和减去m的差最小的子序列
要点：
这题的时间要求是100ms，n的量级是10^5，O(n^2)是肯定不行了，但我一开始算了一下O(nlogn)觉得不大行，就一直在想O(n)的方法，实际上O(nlogn)=10^5*17=1.7*10^6差不多是行的。接下来二分就行了。
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<sstream>
#include<functional>
#include<algorithm>
using namespace std;
const int INF = 0xfffff;
const int maxn = 100050;
int num[maxn],sum[maxn];
vector<pair<int, int>> res;
int n, m;void binery(int i, int &j, int &tempMin) {int left = i, right = n;while (left < right) {int mid = (left + right) / 2;if (sum[mid] - sum[i - 1] < m) {left = mid+1;} elseright = mid;}j = right;tempMin = sum[j] - sum[i - 1];
}int main() {scanf("%d%d", &n,&m);for (int i = 1; i <= n; i++) {scanf("%d", &num[i]);sum[i] = sum[i - 1] + num[i];}int Min = sum[n];for (int i = 1; i <= n; i++) {int j, tempMin;binery(i, j, tempMin);//cout << j << " " << tempMin << endl;if (tempMin >= m) {if (Min > tempMin) {Min = tempMin;res.clear();res.push_back({ i,j });} else if (Min == tempMin) {res.push_back({ i,j });}}}for (auto x : res) {printf("%d-%d\n", x.first, x.second);}return 0;
}这篇关于PAT1044. Shopping in Mars (25)(二分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
