PTA 甲级 1044 Shopping in Mars

题目链接

思路：前缀和+滑动窗口

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int a[MAXN];int main(){int n,m;cin>>n>>m;//n数量 m金额for(int i=1;i<=n;i++){int t;cin>>t;a[i]=a[i-1]+t;//前缀和}vector<pair<int,int>> ans;int i=1,j=1;//滑动窗口while(i<=j&&j<=n){// printf("%d-%d:%d\n",i,j,a[j]-a[i-1]);if(a[j]-a[i-1]==m){ans.push_back(make_pair(i,j));i++,j++;}else if(a[j]-a[i-1]>m) i++;else j++;if(i>j)j++;}if(ans.size()==0){//存储大于m的最小整数int minNum=8989898;i=1,j=1;while(i<=j&&j<=n){// printf("%d-%d:%d\n",i,j,a[j]-a[i-1]);if(a[j]-a[i-1]>m&&a[j]-a[i-1]<minNum){minNum=a[j]-a[i-1];ans.clear();ans.push_back(make_pair(i,j));i++;}else if(a[j]-a[i-1]==minNum){ans.push_back(make_pair(i,j));i++;}else if(a[j]-a[i-1]>minNum) i++;else j++;if(i>j)j++;}}for(auto &[x,y]:ans){cout<<x<<"-"<<y<<endl;}return 0;
}