题意：
给出n个数和m,问是否能选择一段连续区间使得和为m
如果不能的话，选择和大于m并且和m的差值最小的区间们。
思路：
求出前缀和后，数组一定是单调的，可以枚举区间的右端点，二分找区间的左端点。
代码：
23分
#include<bits/stdc++.h> #include<bitset> using namespace std; typedef long long ll; typedef pair<int,int>PII; const int maxn=1e6+7; ll n,m,a[maxn],sum[maxn]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i]; vector<PII>ans; ll minn=1e9; for(int i=1;i<=n;i++){ ll now=sum[i]-m; int pos=upper_bound(sum+1,sum+1+n,now)-(sum+1); if(sum[pos]==now) ans.push_back({pos+1,i}); if(sum[i]-sum[pos]-m>0) minn=min(minn,(sum[i]-sum[pos]-m)); // cout<<i<<" "<<pos<<endl; } if(ans.size()==0){ for(int i=1;i<=n;i++){ ll now=sum[i]-m; int pos=upper_bound(sum+1,sum+1+n,now)-(sum+1); ll tmp=abs(sum[i]-sum[pos]-m); if(tmp==minn) ans.push_back({pos+1,i}); } } for(int i=0;i<ans.size();i++) cout<<ans[i].first<<"-"<<ans[i].second<<"\n"; return 0; }
wa在测试点3
4 10
8 1 12 11
ans:4-4
满分代码
#include<bits/stdc++.h> #include<bitset> using namespace std; typedef long long ll; typedef pair<int,int>PII; const int maxn=1e6+7; ll n,m,a[maxn],sum[maxn]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i]; vector<PII>ans; ll minn=1e9; for(int i=1;i<=n;i++){ ll now=sum[i]-m; int pos=lower_bound(sum,sum+1+n,now)-(sum); if(sum[pos]==now) ans.push_back({pos+1,i}); else pos--; if(sum[i]-sum[pos]-m>0) minn=min(minn,(sum[i]-sum[pos]-m)); //cout<<i<<" "<<pos<<endl; } //cout<<minn<<endl; if(ans.size()==0){ for(int i=1;i<=n;i++){ ll now=sum[i]-m; int pos=lower_bound(sum,sum+1+n,now)-(sum)-1; if(pos==-1) continue; ll tmp=abs(sum[i]-sum[pos]-m); if(tmp==minn) ans.push_back({pos+1,i}); } } for(int i=0;i<ans.size();i++) cout<<ans[i].first<<"-"<<ans[i].second<<"\n"; return 0; }
