Dirty Deeds Done Dirt Cheap

Created by LXC on Fri Jan 19 20:06:50 2024

https://codeforces.com/problemset/problem/1148/D

ranting: 1800

tag: greedy, sortings

problem

有 $n$ 个整数对 $(a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n)$. 保证 $a_1, b_1, a_2, b_2, \cdots, a_n, b_n$ 两两不相等, 并且均在区间 $[1, 2 \cdot n]$ 内.

好序列的定义:
对于一个序列 $x_1, x_2, \cdots, x_{2k}$, 满足

• $x_1 < x_2 > x_3 < \cdots < x_{2k - 2} > x_{2k - 1} < x_{2k}$ 或
• $x_1 > x_2 < x_3 > \cdots > x_{2k - 2} < x_{2k - 1} > x_{2k}$.

求一个序列 $i_1, i_2, \cdots, i_t$ 满足 $a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \cdots, a_{i_t}, b_{i_t}$ 是好序列.

输出 $t$ 的最大值以及对应的序列 $i_1, i_2, \cdots, i_t$.

$2 \leq n \leq 3 \cdot 10^5$
$1 \leq a_i, b_i \leq 2 \cdot n$
并且所有 $a_i, b_i$ 两两不相等.

solution

对于$a_i < b_i$的分成一组，$a_i > b_i$分成一组，答案选择的是数对较多的一组。

对于$a_i < b_i$的一组，我们按照$b_i$降序排列。

这时$a_i< b_i > a_{i+1} < b_{i+1}$。我们只需要对原数对数组的下标进行排序就行了。

对于$a_i > b_i$的一组，同理。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    for (auto& [i,j]:a) {
        cin >> i >> j;
    }
    vector<int> i1, i2;
    for (int i=0; i<n; i++) {
        if (a[i].first < a[i].second) i1.push_back(i);
        else i2.push_back(i);
    }
    if (i1.size() > i2.size()) {
        sort(i1.begin(), i1.end(), [&](int x, int y) {
            return a[x].second > a[y].second;
        });
        cout << i1.size() << "\n";
        for (int i:i1) {
            cout << i+1 << " ";
        } cout << "\n";
    } else {
        sort(i2.begin(), i2.end(), [&](int x, int y) {
            return a[x].first < a[y].first;
        });
        cout << i2.size() << "\n";
        for (int i:i2) {
            cout << i+1 << " ";
        } cout << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}