p; a) {
int i = 0;
for (int j = 0; j < a.size(); j++) {
if (!j || a[j - 1] != a[j]) a[i++] = a[j];
}
// a[0~i-1] 所有不同的数
return a.begin() + i;
}
// vector<int>::iterator unique(vector<int>& a) {
// int i = 1;
// for (int j = 0; j < a.size(); j++) {
// if (a[i - 1] != a[j]) a[i++] = a[j];
// }
// // a[0~i-1] 所有不同的数
// return a.begin() + i;
// }
int main() {
int n;
cin >> n;
for (int i = 0, x; i < n; i++) {
scanf("%d", &x);
a.push_back(x);
}
sort(a.begin(), a.end());
auto x = unique(a);
for (int i = 0; i < x - a.begin(); i++) {
cout << a[i] << " ";
}
return 0;
}
5
1 2 2 3 3
1 2 3
区间合并
- 按区间左端点排序
- 第二个区间对比第一个区间[st,ed]有三种情况
- 在区间内,不更新
- 与区间交集,ed更新
- 在区间外,st,ed更新,更新计数器
803
803. 区间合并 - AcWing题库
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PLL;
vector<PLL> a;
vector<PLL> merge(vector<PLL> &segs) {
vector<PLL> res;
sort(segs.begin(), segs.end());
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});
return res;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
a.push_back({l, r});
}
auto res = merge(a);
cout << res.size() << endl;
return 0;
}
759 ? ? 格子染色(美团)
759. 格子染色 - AcWing题库
- 读入所有行操作,列操作,并排序
- 合并行区间,合并列区间
- 计算所有行的和 + 列的和 res
- res 减去每个行与每个列之间重合点数量
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
struct Node {
int no, l, r;
bool operator<(const Node& w) const {
if (no != w.no)
return no < w.no;
else if (l != w.l)
return l < w.l;
else
return r < w.r;
}
};
// 用 vector<vector<int>> 会很慢
vector<Node> rows;
vector<Node> cols;
vector<Node> merge(vector<Node> segs) {
vector<Node> res;
int no = -2e9, st = -2e9, ed = -2e9;
for (auto seg : segs) {
if (st != -2e9 && no != seg.no) {
res.push_back({no, st, ed});
no = seg.no;
st = seg.l;
ed = seg.r;
} else {
no = seg.no;
if (seg.l > ed) {
if (st != -2e9) res.push_back({no, st, ed});
st = seg.l;
ed = seg.r;
} else {
ed = max(seg.r, ed);
}
}
}
if (ed != -2e9) res.push_back({no, st, ed});
return res;
}
int main() {
int n;
cin >> n;
// 步骤1 输入
while (n--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2) {
rows.push_back({x1, min(y1, y2), max(y1, y2)});
} else {
cols.push_back({y1, min(x1, x2), max(x1, x2)});
}
}
sort(rows.begin(), rows.end());
sort(cols.begin(), cols.end());
// 步骤2 合并区间
rows = merge(rows);
cols = merge(cols);
// 步骤3 计算
long long res = 0; // 最大值可以是 (2e9)平方=4e18
for (int i = 0; i < rows.size(); i++) {
res += rows[i].r - rows[i].l + 1;
}
for (int i = 0; i < cols.size(); i++) {
res += cols[i].r - cols[i].l + 1;
}
// 步骤4 去重
for (int i = 0; i < rows.size(); i++) {
for (int j = 0; j < cols.size(); j++) {
auto row = rows[i];
auto col = cols[j];
if (row.l <= col.no && row.r >= col.no && col.l <= row.no &&
col.r >= row.no)
res--;
}
}
cout << res;
return 0;
}