1049 數列的片段和 (20 分)
給定一個正數數列，我們可以從中截取任意的連續的幾個數，稱為片段，例如，給定數列 { 0.1, 0.2, 0.3, 0.4 }，我們有 (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 這 10 個片段，
給定正整數數列，求出全部片段包含的所有的數之和，如本例中 10 個片段總和是 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0，
輸入格式：
輸入第一行給出一個不超過 10^?5 的正整數 N，表示數列中數的個數，第二行給出 N 個不超過 1.0 的正數，是數列中的數，其間以空格分隔，
輸出格式：
在一行中輸出該序列所有片段包含的數之和，精確到小數點后 2 位，
輸入樣例：
4
0.1 0.2 0.3 0.4
輸出樣例：
5.00
解題思路：
每次依次取片段，先從0.1取到0.4，后從0.2取到0.4，再從0.3取到0.4，以此類推，把每次取到的片段，做累加和即可
代碼示例：
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>
using namespace std;
int main()
{
int n;
cin >> n;
vector<float> nums;
for (int i = 0; i < n; i++)
{
float temp;
cin >> temp;
nums.push_back(temp);
}
//利用accumulate范圍求和函式，其區間為左閉右開
//accumulate(_first,_end,每次累加值value);
double sum = 0.0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j <= n; j++)
{
sum += accumulate(nums.begin() + i, nums.begin() + j, 0.0);
}
}
printf("%.2f\n", sum);
}
運行結果：
超時
優化演算法：
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long sum = 0;
double temp;
for (int i = 0; i < n; i++) {
cin >> temp;
//這里這樣寫的原因是應為,double型別會損失精度,在這題里面,會報錯,所以,我們要用longlong 然后在除
sum += (long long)(temp * 1000) * (i + 1) * (n - i);
}
printf("%.2f", sum / 1000.0);
return 0;
}
再次運行：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/289194.html
標籤：其他
上一篇：C語言基礎-程式員買房子問題
下一篇：作業中的好習慣