PAT甲级1044.

目录

A1044

题目

样例

样例1

输入:

16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13

输出:

1-5
4-6
7-8
11-11

样例2

输入:

5 13
2 4 5 7 9

输出:

2-4
4-5

思路和坑点

　　使用数组sum记录数据sum[0]初始化为0，sum[u]表示样例数据中从第1个到第u个的和，那么记需要支付的的数值为pay，使用两点法指针i和j，如果存在sum[i]-sum[j]==pay，则输出i+1~j；如果小于，则j++；如果大于，则i++，同时还要考虑如果都大于的情况需要，支付的时候使用大于pay但是最接近pay的支付数值来达到最小损失，因此每次记录，大于pay的所有备选值中的最小数，作为新的支付方案，如果有都大于pay（用cnt记录是否有刚好等于pay的记录），则对新的支付方案进行查询。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,pay,cnt=0;                    //pay为需要支付的数值，cnt用于等于pay的计数 
vector<int> sum;                    //保存数据，sum[0]初始化为0 
int find(int p){
    int i=0,j=1,first=1000000000;
    for(;i<=j&&j<sum.size();){        //两点法 i，j指针以前一后 
        int temp=sum[j]-sum[i];        //计算i-j区间内的数值 
        if(temp<p)                    //如果小于pay，j++ 
            j++;
        else if(temp==p){            //如果等于pay，输出并计数 
            printf("%d-%d\n",i+1,j);j++;cnt++; 
        }
        else{                        //如果大于pay，i++，同时记录可能的新方案 
            first=min(first,temp);
            i++;
        }     
    }
    return first;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    scanf("%d%d",&n,&pay);
    sum.resize(n+1);sum[0]=0;
    for(int i=1;i<=n;i++){            //直接读入并计算和记录sum 
        int temp;
        scanf("%d",&temp);
        sum[i]=sum[i-1]+temp;
    } 
    int newpay=find(pay);            //输出，并获得可能的新支付方案 
    if(cnt==0)                        //如果pay的支付不存在，按照新的支付方案进行查询，此处的左值newpay只是为了接应新方案的返回值 
        newpay=find(newpay);
    return 0;
}