F. Sorting (排序,浮点数精度) [2017 CCPC China-Hunan Invitional]

Description

Bobo has $n$tuples$(a_1, b_1, c_1), (a_2, b_2, c_2), \dots, (a_n, b_n, c_n)$ . He would like to find the lexicographically smallest permutation $p_1, p_2, \dots, p_n$of$1, 2, \dots, n$ such that for$i \in {2, 3, \dots, n}$ it holds that $$ \frac{a_{p_{i - 1}} + b_{p_{i - 1}}}{a_{p_{i - 1}} + b_{p_{i - 1}} + c_{p_{i - 1}}} \leq \frac{a_{p_i} + b_{p_i}}{a_{p_i} + b_{p_i} + c_{p_i}} $$

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer $n$.

The $i$-th of the following $n$lines contains $3$integers $a_i$,$b_i$ and$c_i$.

Output

For each test case, print $n$integers$p_1, p_2, \dots, p_n$ seperated by spaces. DO NOT print trailing spaces.

Constraint

  • $1 \leq n \leq 10^3$
  • $1 \leq a_i, b_i, c_i \leq 2 \times 10^9$
  • The sum of $n$does not exceed$10^4$.

Sample Input

2
1 1 1
1 1 2
2
1 1 2
1 1 1
3
1 3 1
2 2 1
3 1 1

Sample Output

2 1
1 2
1 2 3

题解

题目大意

给你 $n$个三元组,要求给出这 $n$个三元组的一个排列,使得对$i \in \left { 2, 3, \cdots, n \right }$ 都满足题给关系。

分析

题给关系中的不等式只涉及 $p_{i - 1}$和$p_{i}$ 两个元素,实际上相当于对三元组重载了小于号。因此,本题实际上是对读入的三元组序列进行排序。因此,我们用一个Node结构体存储三元组的三个变元和读入时在原序列中的位置即可。

struct Node {
    long long a, b, c;
    int id;
}

同时,在比较三元组关系时,因为本题数据卡精度较严,因此不能用double,而应交叉相乘再比较,同时在这过程中约去一些相同的项(避免爆long long)。 $$ (a_{p_{i-1}}+b_{p_{i-1}})(a_{p_{i}}+b_{p_{i}}+c_{p_{i}}) \leq (a_{p_{i}} + b_{p_{i}})(a_{p_{i-1}}+b_{p_{i-1}}+c_{p_{i-1}})) $$

$$ (a_{p_{i-1}} + b_{p_{i-1}})c_{p_{i}} \leq (a_{p_{i}} + b_{p_{i}})c_{p_{i-1}} $$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
typedef long long ll;

struct Node {
    ll a, b, c;
    int id;

    bool operator < (const Node& x) const {
        ll q1 = c * (x.a + x.b);
        ll q2 = x.c * (a + b);

        if(q2 == q1) return id < x.id;
        else return q2 < q1;
    }
} t[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0;
    while(cin >> n) {
        for(int i = 1; i <= n; i++) {
            cin >> t[i].a >> t[i].b >> t[i].c;
            t[i].id = i;
        }

        sort(t + 1, t + n + 1);

        for(int i = 1; i <= n; i++)
            if(i != n) cout << t[i].id << " ";
            else cout << t[i].id << endl;
    }

    return 0;
}
updatedupdated2022-05-212022-05-21