int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed < seg.first) { if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res; }
快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13
voidquick_sort(int q[], int l, int r) { if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
归并排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidmerge_sort(int q[], int l, int r) { if (l >= r) return;
int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中,寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;