C48-时间复杂度+一维前缀(简单)

原题链接：28705.NoteSC++

1943

2025-03-16 20:22:45

发布于：江苏

16阅读

0回复

0点赞

一、枚举优化

继续优化掉一层循环，利用已知的公式进行推倒计算。

参考程序

#include<iostream>
using namespace std;
int main()
{
	int n = 100;
	int cnt = 0;
	for (int i=0; i<=n/7; i++) 		//公鸡
	{
		int j = (n - 7*i)/4;		//母鸡
		int k = n - i - j;		//小鸡
		cnt ++;
		if(k%3==0 && (n - 7*i)%4 == 0)
		{
			printf("%d %d %d\n", i, j, k);
		}
	}
	printf("cnt = %d\n", cnt);
	return 0;
}

二、时间复杂度

表示程序的运行效率。用来衡量一个算法程序完成任务的时间长短。

三、一维前缀和

实例：买书问题

#include<iostream>
using namespace std;

int n, m, a[1005], t; 

int main(){
	cin >> n;
	for (int i=1; i<=n; i++) cin>>a[i];
	cin >> m;
	for (int j=1; j<=m; j++){
		int sum = 0;	
		cin >> t;
		for (int i=1; i<=t; i++){
			sum += t;
		} 
		cout << sum << endl; 
	}
	
	return 0;
}

前缀和（数组）：包含当前元素之前的所有数字之和

前缀和优化版本参考程序，时间复杂度为 O(n)

#include<iostream>
using namespace std;

int n, m, a[1005], t; 
int s[1005]; 

int main(){
	cin >> n;
	for (int i=1; i<=n; i++){
		cin>>a[i];
		s[i] = s[i-1] + a[i]; 	//预处理前缀和数组 
	}
	cin >> m;
	for (int j=1; j<=m; j++){
		cin >> t;
		cout << s[t] << endl; 
	}

	return 0;
}