PAT1049

两个知识点: long double问题 与 c++中保留小数点后位数 #include

暴力解测试点2和3会超时

#include
#include 
using namespace std;
int main() {
	int n = 0;
	cin >> n;
	double* num = new double[n];
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	double sum = 0;
	double result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			sum += num[j];
			result += sum;
		}
		sum = 0;
	}
	cout << fixed << showpoint << setprecision(2) << result << endl;
	//cout << result;
}

转而使用数学归纳法寻找统一解的公式

即: m * ( n - i )( i + 1 );

时间复杂度改进为0(n)的第一次尝试:

测试点2出现错误: 该错误类型是第一次遇见

//先使用数学归纳, 再根据推导出的公式进行编译
#include
#include 
using namespace std;
int main() {
	int n = 0;
	cin >> n;
	double m = 0;
	double result = 0;
	for (int i = 0; i < n; i++) {
		cin >> m;
		result += m * (n - i) * (i + 1);
	}
	cout << fixed << showpoint << setprecision(2) << result << endl;
}

看了这位博主的blog,

(17条消息) PAT1049测试点2的坑_MIIEo-CSDN博客

发现错误原因是:  

double精度不足以满足m这个小于1.0的正数的位数

首先,因为题中未告知m实际位数,为满足可能出现的边界条件,故浮点数精度固然是越大越好;

其次,在c++中,整形*浮点数,结果会向浮点数方向偏移,很可能即使n-i与i+1的乘积足够大,足够让小数变成整数的大,但结果还是要带上尾巴,就像.000000000的一大堆0一样的尾巴

故,解决方法为:  将变量result的double类型改为long double

时间复杂度改进为0(n)的第二次尝试:

//先使用数学归纳, 再根据推导出的公式进行编译
#include
#include 
using namespace std;
int main() {
	int n = 0;
	cin >> n;
	double m = 0;
	long double result = 0;
	for (int i = 0; i < n; i++) {
		cin >> m;
		result += m * (n - i) * (i + 1);
	}
	cout << fixed << showpoint << setprecision(2) << result << endl;
}

最后,还需要注意一下:

c++中保留小数点后位数的命令为:

头文件: #include

具体命令: cout << fixed << showpoint << setprecision(2) << 目标变量 << endl;