Sorting（sort排序）

sorting

题目链接：http://exam.upc.edu.cn/problem.php?id=7039

题意：根据式子进行排序。

其实要是直接弄的话，精度出现问题。

所以需要化简一下：交叉相乘再变化一下。

最后化成        a1×c2    +    b1×c2    <=    a2×c1    +    b2×c1

其实这样已经可以了。

因为很可能出现爆，所以需要long long    或者long double.

这题就完成了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct point{
    ll a,b,c;
    int No;
}p;
p node[10050];
int cmp(p x,p y){
    if((x.a+x.b)*y.c==x.c*(y.a+y.b))
        return x.No<y.No;

    return (x.a+x.b)*y.c<x.c*(y.a+y.b);
}
int main()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&node[i].a,&node[i].b,&node[i].c);
            node[i].No=i;
        }
        sort(node+1,node+1+n,cmp);
        for(int i=1;i<=n;i++){
            printf("%d%c",node[i].No,i==n?'\n':' ');
        }
    }
    return 0;
}

相关阅读

常见十大(内部)排序算法 - Sorting Algorithms C++

基本概念 内部和外部排序 内部排序在这里指的是只用到了电脑内存而不使用外存的排序方式。相对的，外部排序就是同时动用了电脑内

Sorting

Introduction Sorting is ordering a list of objects. We can distinguish two types of sorting. If the number of objects i