本周总结:_C_内存溢出

1.scanf,printf,输入输出,该输入输出方式来源于c,而c++兼容c,并且scanf,printf的运行时间相比cin,cout来说快很多,所以在写程序的时候经常使用scanf,printf
.
2.时间复杂度:算法复杂度就是大致估算程序大致运行的时间,将每一个执行语句看做一个单元,找出其余程序的数学关系,忽略系数与常数,常见复杂度从小到大排序如下:
O(1)

3.二分:

减少循环的次数,将时间复杂度降为O(logn),二分的大致思路就是先根据题目写出一个判断函数,再根据一个值是否符合该函数条件,从而将之后的循环区间缩为[l,r-1]或[l+1,r],达到减少运行时间的目的.用两个大致模板和一道例题来具体说明:

(1):左边界:

while(l

 
(2)右边界: 
while(l>1;
    if(a[mid]<=num) l = mid;//使用a[mid]还是check()看题目要求定
    else r = mid-1;
} 
l+r+1是为了避免出现l与r相邻时出现死循环 
蓝桥1323题例: 
#include
using namespace std;
const int max1 = 1e5+5;
int x[max1];
int y[max1];
int k,n;
int check(int num)//根据题目要求先写check()函数
{
	int sum=0;
	for(int i=0;i=k)
	return 1;
	else
	return 0;
}
int main()
{
	int en=0;
	scanf("%d %d",&n,&k);//输入巧克力数,人数
	for(int i=0;i
 
4,一二位前缀和.差分: 
一维前缀和: 
一维前缀和就是对应一维数组前几项的和,如一个数组a[n](从n=1开始赋值); 
s[2]=a[1]+a[2]; 
s[4]=a[1]+……+a[4]; 
前缀和数组s[i]=s[i-1]+a[i] 
要求一维数组某个区间[l,r]的和就不用在遍历数组,而直接输出s[r]-s[l-1]; 
二维前缀和: 
注意:二维前缀和数组可以从下标为一开始读入数据更方便,但是有的时候题目固定的数组没法处理,但是下标从零开始要加入一些特判条件 
#include
using namespace std;
const int n=5,m=4;
int x[n][m] = {{4,5,1,3},//需要进行二维前缀和的数组
             {6,2,4,2},
             {4,1,5,7},
             {2,1,6,9},
             {1,3,7,5}},sum[n][m];
void sum1(){
    sum[0][0] = x[0][0];
    for(int i=1;i
 
一维差分: 
需要配合一维前缀和来完成,如一个数组a[5]={2,5,6,7,8},先对该数组多个不同区间执行+x *** 作,如果直接一个一个区间处理就非常耗时间,这时就可以用差分来处理 
先写一个空数组b[6] = {0}用于对不同区间加的数的处理,然后对b[]数组求前缀和,此时数组b就是不同区间加过数后的结果,再与数组a每一项对应相加即为所求;对数组b处理主要公式b[r]+x;b[l+1]-x; 
但要注意的是数组b最好比a长,不然l+1易溢出或则在执行b[l+1]-x时加个判断; 
但此算法只适用多次处理一次或较少次访问 
二维差分: 
用到了二维前缀和;和一维差分,只不过二维差分需要标记四个位置,即: 
d[n1][m1]+=x; 
d[n2+1][m1]-=x; 
d[n1][m2+1]-=x; 
d[n2+1][m2+1]+=x; 
int d[n+1][m+1];
int x[n][m] = {{4,5,1,3},
             {6,2,4,2},
             {4,1,5,7},
             {2,1,6,9},
             {1,3,7,5}},sum[n][m];
void sum1(){
    sum[0][0] = d[0][0];
    for(int i=1;i
 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/674662.html

本周总结:

发表评论

评论列表（0条）