【資料範圍超限】hdu 6281 sorting

1. unsigned   int   0～4294967295     1e9

2. int   2147483648～2147483647       1e9

3. long long -9223372036854775808~9223372036854775807      1e18

4. unsigned long long的最大值：18446744073709551615         1e19

當感覺自己寫的很全了啊咋還wa的時候就去看看資料，以hdu 6281 為例

這就是個排序問題，計算(a+b)/(a+b+c)之後排序就行了

我們使用乘法(a1+b1)*(a2+b2+c2)<=(a2+b2)*(a1+b1+c1) 來判斷

然後我們估計了一下資料量到1e19，然後我就去輸入1234567891234567895,19位數發現沒爆，我以為就OK的

但是！1e19是20位數！這個錯誤我都犯過兩遍了！

進入這個坑之後，我們還改成double試過，前前後後調了40+min，以為這是個水題心态都有點不好了

最後看了discuss才意識到爆long long了，知道這個問題後就開始對式子變形。一開始是比較c1*(a2+b2+c2)>=c2*(a1+b1+c1)  拿1做差後的，但還是會爆long long

最後是求倒數之後比較  c1*(a2+b2)>=c2*(a1+b1)，就能很好的處理這道題了

感覺今年要是在賽場上遇到這種情況，這道題我們可能放不下，後面的題不确定的也不太敢做，emm,心态得崩

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 1010;
typedef long long ll;

struct Node
{
    ll a, b, c;
    //double r;
    int idx;
}node[maxn];
int n;


bool cmp(Node x, Node y)
{
    if(x.c*(y.a+y.b)==y.c*(x.a+x.b))
        return x.idx<y.idx;
    else return x.c*(y.a+y.b)>=y.c*(x.a+x.b);
}


int main()
{
//    ll a=12345678912345678955;
//    cout<<a<<endl;
    while(scanf("%d", &n) != EOF)
    {

        for(int i = 1; i <= n; i++)
        {
            scanf("%lld%lld%lld", &node[i].a, &node[i].b, &node[i].c);
            //node[i].r = 1.0 * (node[i].a + node[i].b) / (node[i].a + node[i].b + node[i].c);
            node[i].idx = i;
        }
        sort(node + 1, node + n + 1, cmp);
        for(int i = 1; i < n; i++)
        {
            printf("%d ", node[i].idx);
        }
        printf("%d\n", node[n].idx);
    }
    return 0;
}