1044 Shopping in Mars（枚举二分)

1044 Shopping in Mars（枚举&二分)

思路：枚举$+$二分。

假设答案区间为$[l,r]$，预处理出前缀和，因为前缀和的非递减性。

因此，对于每个$l$，可以进行二分找到最小大于等于$m$的$r$。

时间复杂度：$O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int n,m,a[N];
void fun(int i,int &j,int &sum){
    int l=i,r=n;while(l<r){
    int mid=(l+r)>>1;if(a[mid]-a[i-1]>=m) r=mid;else l=mid+1;}j=r;sum=a[j]-a[i-1];
}
int main(){
    scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){
    scanf("%d",&a[i]),a[i]+=a[i-1];}int mx=a[n];vector<int>ans;for(int i=1;i<=n;i++){
    int j,sum;fun(i,j,sum);if(sum>=m&&sum<=mx){
    if(sum<mx){
    ans.clear();mx=sum;}ans.pb(i),ans.pb(j);}}for(int i=0;i<ans.size();i+=2){
    printf("%d-%d\n",ans[i],ans[i+1]);}return 0;
}