首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; using namespace std; int main() {     int n,k;     int res = 0;     cin &gt;&gt; n &gt;&gt; k;     int arr[n+1];     int num;     arr[0] = 0;     for(int i = 1;i &lt;= n;++i)     {         cin &gt;&gt; num;         arr[i] = arr[i-1] + num;     }     for(int i = 1;i &lt;= n;++i)     {         for(int j = i;j &lt;= n;++j)         {             if(arr[j] - arr[i-1] &lt;= k) ++res;             else break;         }     }     cout &lt;&lt; res; }</pre>
这道题暂未补解析。