题目链接：点击打开链接
题目大意：找到价值正好等于 m 的子序列下标 “L-R”，若有多个，都输出；若一个也没有，则输出相差最小的（有多个，都输出）。
解题思路：差分前缀和 + 二分查找。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1e5+10; ll a[maxn], b[maxn]; unordered_map<ll,int> ump; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { b[0]=0; ump[0]=-1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]+=a[i]+b[i-1]; ump[b[i]]=i; } // for(int i=0;i<=n;i++) printf("%d ",b[i]); puts(""); int f=1; for(int i=1;i<=n;i++) { ll idx=b[i]-m,l,r=i; if(idx>=0 && (ump[idx]>0 || ump[idx]==-1)) // 匹配到正好的前缀和 { f=0; l=ump[idx]==-1?ump[idx]+2:ump[idx]+1; printf("%lld-%lld\n",l,r); } } if(f) // 没有匹配到正好的前缀和 { ll mi=INT_MAX; for(int i=1;i<=n;i++) // 查找最小值 { ll idx=b[i]-m,l,r=i; if(idx<0) continue; l=upper_bound(b,b+n+1,idx)-b; mi=min(b[r]-b[l-1],mi); } for(int i=1;i<=n;i++) // eq 最小值输出 { ll idx=b[i]-m,l,r=i; if(idx<0) continue; l=upper_bound(b,b+n+1,idx)-b; if(mi==b[r]-b[l-1]) printf("%lld-%lld\n",l,r); } } } return 0; }
