首页 > 代码库 > PAT 1044. Shopping in Mars
PAT 1044. Shopping in Mars
#include <cstdio>#include <cstdlib>#include <vector>#include <climits>#include <algorithm>using namespace std;int main() { int N, M; scanf("%d%d", &N, &M); vector<int> nums(N); vector<pair<int, int> > cuts; for (int i=0; i<N; i++) { scanf("%d", &nums[i]); } int p = 0; int q = 0; int csum = nums[0]; int lsum = INT_MAX; while (p<=q && q < N) { if (csum < M) { if (q+1 >= N) { break; } csum += nums[++q]; } else if (csum == M) { if (lsum > csum) { cuts.clear(); } lsum = csum; cuts.push_back(make_pair(p, q)); if (q+1 >= N) { break; } csum -= nums[p++]; csum += nums[++q]; } else { if (csum < lsum) { cuts.clear(); lsum = csum; cuts.push_back(make_pair(p, q)); } else if (csum == lsum) { cuts.push_back(make_pair(p, q)); } if (p == q && (q + 1 < N)) { csum += nums[++q]; } csum -= nums[p++]; } } sort(cuts.begin(), cuts.end()); int len = cuts.size(); for (int i=0; i<len; i++) { printf("%d-%d\n", cuts[i].first + 1, cuts[i].second + 1); } return 0;}
一根爬虫
PAT 1044. Shopping in Mars
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。