简答题
偏难
#7564
买地攻略 数码城市有土地出售。待售的土地被划分成若干块,每一块标有一个价格。这里假设每块土地只有两块相邻的土地,除了开头和结尾的两块是只有一块邻居的。每位客户可…
买地攻略
数码城市有土地出售。待售的土地被划分成若干块,每一块标有一个价格。这里假设每块土地只有两块相邻的土地,除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价,请你编写程序,根据客户手头的现金量,告诉客户有多少种不同的购买方案。
时间限制: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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
int res = 0;
cin >> n >> k;
int arr[n+1];
int num;
arr[0] = 0;
for(int i = 1;i <= n;++i)
{
cin >> num;
arr[i] = arr[i-1] + num;
}
for(int i = 1;i <= n;++i)
{
for(int j = i;j <= n;++j)
{
if(arr[j] - arr[i-1] <= k) ++res;
else break;
}
}
cout << res;
}</pre>
这道题暂未补解析。