CF1601D Difficult Mountain

Alex_Wei · 2021-11-05 19:18:25 · 题解

CF1601D. Difficult Mountain 2700

一般这种神仙贪心题都做不来。

把所有登山者分成两类：一类是 a_i\leq s_i 的记为集合 S，一类是 s_i<a_i 的记为集合 T。前者内部互不干扰，而后者可以按照 a_i 从小到大排序贪心。观察 S 对 T 的影响，对于 i\in S，j\in T，若 s_j<a_i\leq s_i<a_j，那么 i,j 之间只能选一个，显然选 i 更优因为 a_i<a_j，其他情况下可以证明 i,j 可以同时选择。

如果将所有 (s_i,a_i) 按照 \max(a_i,s_i) 为第一关键字，s_i 为第二关键字（主要考虑到 s_j<a_i\leq s_i=a_j 的情况，此时 j 应先被选）排序，那么对于上面的特殊情况，i 一定先于 j 被选。故排序后直接贪心就行，时间复杂度 \mathcal{O}(n\log n)。

const int N = 5e5 + 5;
int n, d, ans;
struct node {
    int s, a, mx;
    bool operator < (const node &v) const {
        return mx != v.mx ? mx < v.mx : s < v.s;
    }
} c[N];
int main(){
    cin >> n >> d;
    for(int i = 1; i <= n; i++) {
        cin >> c[i].s >> c[i].a, c[i].mx = max(c[i].s, c[i].a);
        if(c[i].s < d) i--, n--;
    } sort(c + 1, c + n + 1);
    for(int i = 1; i <= n; i++) if(c[i].s >= d) cmax(d, c[i].a), ans++;
    cout << ans << endl;
    return 0;
}