3.7排序&查找练习&时间空间复杂度
3.7排序&查找练习&时间空间复杂度
目录- 3.7排序&查找练习&时间空间复杂度
- P1478 陶陶摘苹果（升级版）
- P1918 保龄球
- P1678 烦恼的高考志愿
- P2249 【深基13.例1】查找
- P1923 【深基9.例4】求第 k 小的数
- P7910 [CSP-J 2021] 插入排序
- 时间复杂度&空间复杂度
洛谷题目传送门
- P1478 陶陶摘苹果（升级版）
- P1918 保龄球
- P1678 烦恼的高考志愿
- P2249 【深基13.例1】查找
- P1923 【深基9.例4】求第 k 小的数
- P1102 A-B 数对
- P7910 [CSP-J 2021] 插入排序
P1478 陶陶摘苹果（升级版）
#include
using namespace std;
const int N=5e5+10;
struct T{ double x,y; }t[N];
bool cmp(T a, T b){ return a.y>n>>s>>a>>b;//题目未给出数据类型，double保险
for(int i=1; i<=n; i++) cin>>t[i].x>>t[i].y;
sort(t+1, t+1+(int)n, cmp);//这里的n参数应当为整型，于是强制转换
for(int i=1; i<=n; i++){
if(t[i].x <= a+b && t[i].y<=s){ s-=t[i].y; ans++; }
}
cout< P1918 保龄球
#include
using namespace std;
const int N=1e5+1;
struct T{ int id, value; }t[N];
bool cmp(T a, T b){ return a.valuem) r=mid-1;
else if(arr[mid].value==m) return arr[mid].id;
}
return 0;
}
int main(){
int n,v; scanf("%d", &n);
for(int i=1; i<=n; i++){ scanf("%d", &v); t[i].id=i, t[i].value=v; }
sort(t+1, t+n+1, cmp); int q,m; scanf("%d", &q);
while(q--){
scanf("%d", &m); printf("%d\n", binSearch(t, n, m));
} return 0;
}
P1678 烦恼的高考志愿
#include
using namespace std;
const int N=1e5+1;
int a[N], b[N];
int binSearch(int arr[], int n, int m){
int l=1,r=n, mid;
while(l=m) r=mid;
}
if(r>1 && abs(arr[r-1]-m) < abs(arr[r]-m)) r=r-1; //找差距最小的元素下标
return r;
}
int main(){
int m,n; cin>>m>>n;
for(int i=1; i<=m; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
sort(a+1, a+1+m); long long ans=0;
for(int i=1; i<=n; i++){
int id = binSearch(a, m, b[i]); ans += abs(a[id]-b[i]);
}
printf("%lld\n", ans); return 0;
}
P2249 【深基13.例1】查找
#include
using namespace std;
const int N=1e6+10;
int n,m,a[N], b[N];
int binSearch(int* arr, int x){
int l=1, r=n,mid;
while(l<=r){
mid=(l+r)/2;
if(arr[mid]x) r=mid-1;
else if(arr[mid]==x){
if(mid>1 && arr[mid-1]==x) r=mid-1;
else return mid;
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=m; i++) cin>>b[i];
for(int i=1; i<=m; i++) printf("%d ", binSearch(a, b[i]));
return 0;
}
P1923 【深基9.例4】求第 k 小的数
#include
using namespace std;
const int N=5e6+10;
int a[N], n, k;
void quickSort(int*arr, int l, int r){
if(l>=r) return;
int i=l, j=r, mid=arr[l];
while(imid) j--; a[i]=a[j];
while(i=i+1) quickSort(arr, i+1, r);
}
int main(){
scanf("%d%d", &n, &k);
for(int i=0; i P7910 [CSP-J 2021] 插入排序
#include//50分,超时
using namespace std;
const int N=1e4;
struct T{ int id, value; }a[N], b[N];
bool cmp(T a, T b){ return a.value=2; j--){
if(arr[j].value < arr[j-1].value){
T t = arr[j-1]; arr[j-1] = arr[j]; arr[j] = t;
}
}
}
}
int main(){
int n,q; scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++){ scanf("%d", &a[i].value); a[i].id=i; }
for(int i=1; i<=q; i++){
int f,x,v; scanf("%d%d", &f, &x);
if(f==1){
scanf("%d", &v); a[x].value=v;
}else if(f==2){
for(int i=1; i<=n; i++) b[i]=a[i];
insertSort(b, n);
cout< 满分解法参考
时间复杂度&空间复杂度
在进行算法分析时，语句总的执行次数 \(T(n)\) 是关于问题规模n的函数，进而分析 \(T(n)\) 随 \(n\) 的变化情况并确定 \(T(n)\) 的数量级。
算法的时间复杂度，也就是算法的时间量度，记作：\(T(n}=O(f(n))\), 这样的表示方法被称为大\(O\)表示法。
它表示随问题规模 \(n\) 的增大，算法执行时间的增长率和 \(f(n)\) 的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。
其中 \(f(n)\) 是问题规模n的某个函数。
算法时间复杂度：
\[O(1)举例：对一个数据集中的N个元素进行排序，N<1e7。
当我们使用插入排序对数据集进行排序时，程序如下：
for(int i=1; i<=n; i++){ //执行次数：n
for(int j=i; j>1; j--){ //执行次数：n + n-1 + n-2 +...+ 1 = (1+n)*n/2
if(arr[j]上述程序总的执行次数：\(n+3*(1+n)*n/2 = O(n^2)\)；这时候需要取大头 \(n^2\)。
当N=1e7时，=1e14 > 5e8，故该算法不是正解，需要考虑其他的解法。
空间复杂度同样是对所在空间进行估计，但是由于程序的确定，那么一般空间大小就确定了，当然动态空间除外。
可以对所用空间的主要部分进行估算，不超过限制空间大小即可。sizeof(a)/1024.0/1024<<"MB";