A30950. 买地攻略数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。 104）为土地分割的块数（于是这些…
填空题
中等
知识点
题目描述
买地攻略
数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。
时间限制：8000 内存限制：262144
输入
输入首先在第一行给出两个正整数：N（≤ 104）为土地分割的块数（于是这些块从 1 到 N 顺次编号）；M（≤ 109）为客户手中的现金量。 随后一行给出 N 个正整数，其中第 i 个数字就是第 i 块土地的标价。 题目保证所有土地的总价不超过 109。
输出
在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。
样例输入
5 85
38 42 15 24 9
样例输出
11
样例解释
这 11 种不同的方案为： 38 42 15 24 9 38 42 42 15 42 15 24 15 24 15 24 9 24 9
参考答案
#include<iostream>
using namespace std;
int main(){
int n,m; //n块地 m块钱
long long a[10005]={0}; //a[i]前i块地的前缀和
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[i]=a[i-1]+x; //前缀和
}
int cnt=0;
for(int i=1;i<=n;i++){ //从i开始
for(int j=i;j<=n;j++){ //到j的土地
if(a[j]-a[i-1]<=m){ //够钱买
cnt++;
}else break; //不够钱，后面更多土地就更不够了
}
}
cout<<cnt;
}
上一题
下一题