中山专业制作网站,外贸论坛有哪些平台,wordpress的图标怎么添加,淄博网站建设设计公司Problem - D2 - Codeforces
题意#xff1a; 思路#xff1a;
大家都说这是典#xff0c;但是我不懂怎么个典法#xff0c;可能堆贪心都是这样做的吗#xff0c;不懂
首先肯定要贪心#xff0c;对于一个坏点#xff0c;优先删除覆盖别的点多的
考虑nlogn做法#x…Problem - D2 - Codeforces
题意 思路
大家都说这是典但是我不懂怎么个典法可能堆贪心都是这样做的吗不懂
首先肯定要贪心对于一个坏点优先删除覆盖别的点多的
考虑nlogn做法先去枚举点然后把覆盖该点的所有区间扔进优先队列里优先删除右端点靠右的
那怎么看是不是坏点还得维护一个差分数组边枚举边维护
感觉突破点就是堆贪心
Code
#include bits/stdc.h#define int long longusing i64 long long;constexpr int N 2e5 10;
constexpr int M 1e6 10;
constexpr int P 2600;
constexpr i64 Inf 1e18;
constexpr int mod 998244353;
constexpr double eps 1e-6;struct ty {int l, r;int id;bool operator (const ty a) const {return a.r r;}
}p[N];std::priority_queuety q;int n, k;
int sum[N];
int ans[N];bool cmp(ty x, ty y) {if (x.l y.l) return x.r y.r;return x.l y.l;
}
void solve() {std::cin n k;for (int i 1; i n; i ) {std::cin p[i].l p[i].r;p[i].id i;sum[p[i].l] ;sum[p[i].r 1] --;}std::sort(p 1, p 1 n, cmp);int j 1;int len 0;for (int i 1; i N; i ) {while (j n p[j].l i) q.push(p[j ]);sum[i] sum[i - 1];while (sum[i] k) {auto u q.top();q.pop();ans[len] u.id;sum[i] --;sum[u.r 1] ;}}std::cout len \n;for (int i 1; i len; i ) std::cout ans[i] \n [i len];
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;while (t--) {solve();}return 0;
}
