关于算法-数据结构:PAT甲级2020年秋季考试-72-How-Many-Ways-to-Buy-a-Piece-of-Land

7-2 How Many Ways to Buy a Piece of Land (25 分)

The land is for sale in CyberCity, and is divided into several pieces. Here it is assumed that each piece of land has exactly two neighboring pieces, except the first and the last that have only one. One can buy several contiguous（间断的）pieces at a time. Now given the list of prices of the land pieces, your job is to tell a customer in how many different ways that he/she can buy with a certain amount of money.

Input Specification:

Each input file contains one test case. Each case first gives in a line two positive integers: N (≤10​4​​), the number of pieces of the land (hence the land pieces are numbered from 1 to N in order), and M (≤10​9​​), the amount of money that your customer has.

Then in the next line, N positive integers are given, where the i-th one is the price of the i-th piece of the land.

It is guaranteed that the total price of the land is no more than 10​9​​.

Output Specification:

For each test case, print the number of different ways that your customer can buy. Notice that the pieces must be contiguous.

Sample Input:

5 85
38 42 15 24 9

Sample Output:

11

Hint:

The 11 different ways are:

38
42
15
24
9
38 42
42 15
42 15 24
15 24
15 24 9
24 9

题目限度：

题目粗心：

现有 N 块土地，总预算为 M 元，请问购买多少一连串的土地。

算法思路：

题目的提醒很显著了，其实就是该数字串中的子串和有多少个是小于等于 M 的，那么咱们应用 price 数组保留每一块土地的价格，而后遍历每一块土地作为一连串土地的终点，应用 total_price 保留当期土地 price[i] 作为终点的价格局部和，只有不大于 M，那么就阐明以后的数字子串为一种解，而后累加前面一块土地的价格，最终输入最终解决方案即可

提交后果：

AC 代码：

#include<cstdio>

using namespace std;

int N,M;// 土地块数，总预算
int price[10005];

int main(){scanf("%d %d",&N,&M);
    for (int i = 0; i < N; ++i) {scanf("%d",&price[i]);
    }
    int ways = 0;
    for(int i=0;i<N;++i){// 每一块土地作为终点
        if(price[i]>M) continue;
        int total_price = price[i];
        ++ways;
        for(int j=i+1;j<N;++j){total_price += price[j];
            if(total_price>M) break;
            ++ways;
        }
    }
    printf("%d",ways);
    return 0;
}