首页 > 代码库 > PAT-1044. Shopping in Mars (25)
PAT-1044. Shopping in Mars (25)
这道题木意思是给你一个连续的序列，要求找出其中连续和为给定值的一段序列，如果不存在这样的序列，那么就输出值大于给定值且最接近的这样值的一个序列。
题目数据量是10^5,如果用N*2复杂度肯定会超时，所以我采用的是On算法。但是在求和少于给定值的过程中所需的步骤不确定。总体效果还算不错，最大时间是39ms。
自己挖了一坑。。。
#include "stdafx.h"#include<iostream>#include<vector>using namespace std;struct Pair{int x;int y;Pair(int x,int y){this->x=x;this->y=y;}};vector<Pair> v;int main(){int n,m;int start=1;int data[100100];int sum=0;freopen("1044.txt","r",stdin);int dis=0xffffffff>>1;while(scanf("%d%d",&n,&m)!=EOF){bool flag=false;for(int i=1;i<=n;i++){scanf("%d",&data[i]);sum+=data[i];while(sum>m){if(sum>m&&sum-m<dis){dis=sum-m;v.clear();v.push_back(Pair(start,i));}else if(sum>m&&sum-m==dis){v.push_back(Pair(start,i));}sum-=data[start]; //先进行减法，然后再判断，导致两个数据不正确。start=start+1;}if(sum==m){printf("%d-%d\n",start,i);sum-=data[start];start=start+1;flag=true;}}if(!flag){for(int i=0;i<v.size();i++){printf("%d-%d\n",v[i].x,v[i].y);}}}return 0;}
PAT-1044. Shopping in Mars (25)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。