1120 买地攻略 – PAT乙级真题

数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。

现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。

输入格式：

输入首先在第一行给出两个正整数：N（≤10^4）为土地分割的块数（于是这些块从 1 到 N 顺次编号）；M（≤10^9）为客户手中的现金量。

随后一行给出 N 个正整数，其中第 i 个数字就是第 i 块土地的标价。

题目保证所有土地的总价不超过 10^9。

输出格式：

在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。

输入样例：

5 85
38 42 15 24 9

输出样例：

样例解释：

这 11 种不同的方案为：

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

分析：使用pre数组保存土地价格前缀和，pre[i]表示从第一个土地到第i个土地的总价。在计算从第j个房子到第i个土地的总价的时候，只需要计算pre[i]-pre[j-1]即可。两个for循环，枚举所有i与j的值，然后计算出可以购买的方案数量即可。喵喵喵~

#include <iostream>
using namespace std;
int N, M, ans, a, pre[10005];
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> a;
        pre[i] = pre[i - 1] + a;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            if (pre[j] - pre[i - 1] <= M) ++ans;
            else break;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int N, M, ans, a, pre[10005];

int main(){

cin >> N >> M;

for (int i = 1; i <= N; i++) {

cin >> a;

pre[i] = pre[i - 1] + a;

}

for (int i = 1; i <= N; i++) {

for (int j = i; j <= N; j++) {

if (pre[j] - pre[i - 1] <= M) ++ans;

else break;

}

cout << ans;

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版