AcWing 算法基础课week 1 总结
总结点 1：快速排序（分治思想）
题1：从小到大排序
主体思路：定义一个数x属于数组s，利用双指针，将数组分为大于等于x和小于等于x的两部分，然后递归处理。（具体步骤如下）
1.
如上图所示，我们定义一个数组s用来储存n个数据，然后定义两个指针i j,分别指向数组的左右两端，同时i指针逐个向右移动扫描数组，j指针同理向左。
2.
当i,j指针扫描的过程中，当s>x时，指针i就停止移动，同理当s[j] x); if (i < j)swap(s, s[j]);//交换两值 } quick_sort(s, l, j);//递归处理左右两边 quick_sort(s, j + 1, r);}int main(){ cin >> n; for (int i = 0; i < n; i++) { cin >> s; } quick_sort(s, 0, n - 1);//将s[]数组的l-r区间内的数据排序 for (int i = 0; i < n; i++) { cout 1]; while (i < j) { do i++; while (s < x); do j--; while (s[j] > x); if (i < j)swap(s, s[j]); } int sl = j - l + 1;//计算左边部分有多少个数 if (k > n >> k; for (int i = 0; i < n; i++) { int x; cin >> x; s.push_back(x); } cout 1;merge_sort(s,l,mid);merge_sort(s,mid+1,r);[/code]2.
合并两个数组。利用两个指针i,j分别指向两个数组的起始位置，如果s n; } while (q--) { int x; cin >> x; int l = 0, r = n - 1;//设置左右边界 while (l < r)//找到左边界 { int mid = l + r >> 1; if (s[mid] >= x)r = mid; else l = mid + 1; } if (s[l] != x)//如果没有X就输出-1 -1 { cout =0;i--) { if(a!=b) return a>b; }}[/code]下面是完整代码：- while(i<j)
- {
- do i++;while(s[i]<x);//i指针向右移动，当s[i]>x,移动停止，j同理
- do j--;while(s[j]>x);
- if(i<j)swap(s[i],s[j]);//如果i<j说明s[j]<x<s[i],就进行交换
- }
- quick_sort(s,l,j);
- quick_sort(s,j+1;r);
[code]vector div(vector &a, int &b,int &r){ vector c; for (int i = a.size() - 1; i >= 0; i--) { r = r * 10 + a; c.push_back(r / b); r %= b; } reverse(c.begin(), c.end()); while (c.size() > 1 && c.back() == 0)c.pop_back(); return c;}int main(){ string x; int b; cin >> x >> b; vector a; for (int i = x.size() - 1; i >= 0; i--)a.push_back(x - '0'); int r = 0; auto c = div(a, b,r); for (int i = c.size() - 1; i >= 0; i--) { cout > m; vector s(n + 1); s[0] = 0; for (int i = 1; i < n + 1; i++) { cin >> s; } vector a; a.push_back(0); for (int i = 1; i > l >> r; cout n >> m; for (int i = 1; i > x; insert(i, i, x);//初始化数组可以看做在i-i之间插入x } while (m--)//m组操作 { int l, r, c; cin >> l >> r >> c; insert(l, r, c); } for (int i = 1; i (减去多余的绿色部分)
由此得出核心代码：
[code] for (int i = 1; i > q; for (int i = 1; i a[j]; } } for (int i = 1; i x1 >> y1 >> x2 >> y2; cout > m >> q; for (int i = 1; i x; insert(i, j, i, j, x); } } while (q--) { int x1, y1, x2, y2,r; cin >> x1 >> y1 >> x2 >> y2 >> r; insert(x1, y1, x2, y2, r); } for (int i = 1; i |
