时间和空间复杂度问题
时间复杂度计算方法:可以理解为循环次数
空间复杂度:空间一维开到5e6+7极限,二维开一般1100*1100。无论几维,总体每个不超1e7。
比如
int a[1100][1100]//合法 int a[11000][11000]//不合法
一维数组的下标问题
int a[10]; for(int i=0;i<10;i++) cout<<a[i]<<endl; //下标可用范围只有0~n-1,不要用n和负数!
数组过大时无法输入的问题
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int a[maxn];//将数组定义在main外 int main(){ return 0; }
memset用法(格式化)
前言:sizeof(x)函数表示返回x的字节大小
memset(vis,0,sizeof(vis));//对数组的初始化操作 数组名,初始化赋值,赋值区域大小
一般初始化为0,1,-1
全局变量的数组自动赋值为0,局部变量开始是随机数。
初始化结构体一般不用memset,因为结构体中还有其他类型的数组如char类型。一般用for循环初始化结构体或是当用到的时候先初始化。
memset(a,b,c); //a表示想要格式化的数组,b想要将数组赋给的值,c想要赋值的长度 //一般情况下b的值为0,1,-1,0x3f(最后一个表示赋值为最大值) //一般情况下,c=sizeof(a),也可简化写成sizeof a
memset(a,-1,sizeof(a));//表示将a数组全部赋值为-1 memset(a,0x3f,sizeof a);///表示将a数组全部赋值为0x3f3f3f3f for(int i=0;i<maxn;i++) a[i]=-1;///等同于第一句
二维数组
看成一维数组套一维数组即可,掌握遍历后可做UPC的排序
结构体
定义
struct node{ char name[100]; char place[100]; int sale; double price; string s; }a[100];
或者
struct node{ char name[100]; char place[100]; int sale; double price; string s; }; node a[100];//可放在main函数里也可放在main函数外
调用:
排序
#include<algorithm>//c++ sort(a,b,c);//位于algorithm库,必须加上此库或是用万能头
其中a为开始排序的位置,b为排序结束的位置,c为排序方式;
默认的排序方式为整数从小到大,如果想按照其他排序方式的话,则需要提前定义。
bool cmp(int a,int b)//一般整数排序 { return a>b; } bool cmp(node a,node b)//一般结构体排序 { return a.x>b.x; }
关于起始位置
for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n);
or
for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n);
例题分析:
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; struct Node{ char name[100]; char place[100]; int sale; }a[1100]; bool cmp(Node a,Node b) { if(strcmp(a.place,b.place) == 0) return strcmp(a.name,b.name)<0; else return strcmp(a.place,b.place)<0; } int main() { int N,M,i; scanf("%d",&N); while(N--) { scanf("%d",&M); int cnt = 0;//计数器 for(i=1;i<=M;i++){ Node tmp;//定义一个同类型的结构体来储存当前的输入数据 scanf("%s%s%d",tmp.name,tmp.place,&tmp.sale); int flag = 0;//用于后面判断tmp是存在于当前结构体还是下一结构体 for(int j=1;j<i;j++) { if(strcmp(tmp.name,a[j].name)==0&&strcmp(tmp.place,a[j].place)==0)//相同产地相同名字 { a[j].sale += tmp.sale;//加到前面的结构体里 flag = 1; break; } } if(!flag) a[++cnt] = tmp;//不同产地不同名字 就把他加到结构体本位里 ,然后计数器自增1 } sort(a+1,a+cnt+1,cmp);//排序 for(i=1;i<=cnt;i++){ if(strcmp(a[i].place,a[i-1].place)!=0)//不同产地 printf("%s\n |----%s(%d)\n",a[i].place,a[i].name,a[i].sale); else if(strcmp(a[i].place,a[i-1].place)==0)//相同产地 printf(" |----%s(%d)\n",a[i].name,a[i].sale); } if(N!=0) printf("\n"); } return 0; }