Paint

题目连接: Paint

大致题意:

有n个篱笆从1到n编号, 有k位艺术家, 每位艺术家都会给某个区间的篱笆涂色, 但是当某位艺术家涂色的区间也有别的艺术家涂色, 那么他就不干活了. 问你最少会有多少个篱笆不被涂色.

解题思路:

赛后才明白就是一个类似于区间合并的问题. 按照左区间或者右区间排序, 然后看看能不能将某段已有的区间接上去.

如果想接在左侧, 那么一定是某个区间的r要小于当前的L, 所以将r从小到大排序即可 一直维护区间长度最大的r在map末尾.

如果想接在右侧, 那么一定是某个区间的l要大于当前的R, 所以将l从大到小排序即可. 一直维护区间长度最小的l在map的开头/

AC代码:

接在左侧

#include <bits/stdc++.h> typedef long long ll; using namespace std; const int MAXN = 2E5 + 10; vector<pair<ll, ll>> v; map<ll, ll> m; //所有的右边界 ll fact(ll l) { ll all = 0; auto temp = m.lower_bound(l); if (temp != m.begin()) all = (--temp)->second; return all; } bool cmp(pair<ll, ll>& a, pair<ll, ll>& b) { return a.second < b.second || (a.second == b.second && a.first < b.first); } int main(void) { ll n, k; scanf("%lld %lld", &n, &k); for (ll i = 1; i <= k; ++i) { ll l, r; scanf("%lld %lld", &l, &r); v.push_back({ l, r }); } sort(v.begin(), v.end(), cmp); //按照右区间从小到大排列 for (auto it = v.begin(); it != v.end(); ++it) { auto op = *it; ll all = op.second - op.first + 1; //得到区间长度 all += fact(op.first); //看看有没有能拼到序列左侧的 if (m.empty() || all > m.rbegin()->second) { m[op.second] = all; } } cout << n - m.rbegin()->second << endl; return 0; }

接在右侧

#include <bits/stdc++.h> typedef long long ll; using namespace std; const int MAXN = 2E5 + 10; vector<pair<ll, ll>> v; map<ll, ll> m; //所有的左边界 ll fact(ll r) { ll all = 0; auto temp = m.lower_bound(r); //找到比他右边界大的左边界 if (temp != m.end()) all += temp->second; return all; } int main(void) { ll n, k; scanf("%lld %lld", &n, &k); for (ll i = 1; i <= k; ++i) { ll l, r; scanf("%lld %lld", &l, &r); v.push_back({ l, r }); } sort(v.begin(), v.end()); for (auto it = v.rbegin(); it != v.rend(); ++it) { auto op = *it; ll all = op.second - op.first + 1; //得到区间长度 //看看有没有能拼在区间右边的 all += fact(op.second); if (m.empty() || all > m.begin()->second) { m[op.first] = all; } } cout << n - m.begin()->second << endl; return 0; }

END