已知有n个动物朋友排成一排,每个动物朋友都有一个正整数的快乐值,涛涛每次会和连续的动物朋友玩,并且获得这些动物朋友快乐值的和的快乐,而涛涛是个完美主义者,他觉得快乐值刚好是m时候才是快乐的,现在请问有多少种选择方式,使得所选的连续的动物朋友的快乐值刚好为m。 输入描述: 第一行输入n(1<=n<=1e6)和m(1<=m<=1e6)。 第二行输入n个正整数,第i个代表第i个动物朋友的快乐值。(1<=ai<=1e5) 输出描述: 一个整数,表示可能存在的选法数量,如果没有,就输出0;用c++来写代码
时间: 2024-04-12 17:28:31 浏览: 53
输入两个正整数m和n,求最小公倍数,与最大公约数.docx
以下是用 C++ 编写的代码实现:
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int count_choices(int n, int m, vector<int>& happiness) {
unordered_map<int, int> prefixSumCount;
int count = 0;
int prefixSum = 0;
for (int i = 0; i < n; i++) {
prefixSum += happiness[i];
if (prefixSum == m) {
count++;
}
if (prefixSumCount.find(prefixSum - m) != prefixSumCount.end()) {
count += prefixSumCount[prefixSum - m];
}
prefixSumCount[prefixSum]++;
}
return count;
}
int main() {
int n, m;
cin >> n >> m;
vector<int> happiness(n);
for (int i = 0; i < n; i++) {
cin >> happiness[i];
}
int result = count_choices(n, m, happiness);
cout << result << endl;
return 0;
}
```
这段代码首先读取输入的 n 和 m,然后读取 n 个动物朋友的快乐值。接下来,调用 `count_choices` 函数来计算可能的选择方式的数量,并将结果输出。
希望对你有所帮助!如果还有其他问题,请随时提问。
阅读全文