1044. Shopping in Mars (25)

双指针，辅助数组存储对应位置信息

#include<iostream>#include<algorithm>#include<vector>#include<map> #include<string>#include<set>using namespace std;const int INF = 100000001;vector<int> num;int main(){	int n, m;	cin>>n>>m;	for(int i = 0; i < n; i++){		int temp;		scanf("%d",&temp);		num.push_back(temp);	}	int low[num.size()];	int valu[num.size()];	int i = 0;	int j = 0;	int sum = 0;	while(i < num.size()){		sum += num[i];		if(sum >= m){			while(sum >= m){				sum -= num[j];				j++;			}			low[i] = --j;//			high[i] = i;			sum += num[j];			valu[i] = sum;		}		i++;	}	int minvalu = INF;	for(int i = 0; i < num.size(); i++){		if(valu[i] != 0 && valu[i] < minvalu){			 minvalu = valu[i];		}	}	for(int i = 0; i < num.size(); i++){		if(valu[i] == minvalu){			PRintf("%d-%d/n",low[i] + 1,i + 1);		}	}	return 0;}