PAT A1044 Shopping in Mars

题目链接

解题思路

1、使用sums[i]表示从0开始到i的前面所有序列的和，那么sums一定是一个严格单调递增的序列。然后使用lower_bound找出第一个大于等于sums[i]+m的下标j，然后打印i+1和j。并找出当前面子序列和刚好大于m时，求最小的差。

2、如果没有正好相等的，就进行第二次遍历，用第一次遍历找出的最小值来判断输出对应的刚好大于的i+1和j下标即可。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=1e9;
const int maxn=1e5+10;
int n,m;
int sums[maxn];//递增和序列
int main(){
    scanf("%d%d",&n,&m);
    int d;
    sums[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&d);
        sums[i]=sums[i-1]+d;
    }
    bool has=false;
    int mind=INF;
    for (int i = 0; i <= n; ++i) {
        int j=lower_bound(sums+i+1,sums+n+1,sums[i]+m)-sums;
        if(sums[j]-sums[i]==m){
            printf("%d-%d\n",i+1,j);
            has=true;
        }else if(sums[j]-sums[i]>m&&sums[j]-sums[i]-m<mind){
            mind=sums[j]-sums[i]-m;
        }
    }
    if (!has){
        for (int i = 0; i <= n; ++i) {
            int j=lower_bound(sums+i+1,sums+n+1,sums[i]+m)-sums;
            if(sums[j]-sums[i]-m==mind){//find the pairs of i-j with Di+……+Dn-m minimized
                printf("%d-%d\n",i+1,j);
            }
        }
    }
    return 0;
}