HDU4442 Physical Examination

2012 Asia JinHua Regional Contest
Problem A. Physical Examination
官方解題報告：
對排在相鄰的兩個任務進行交換然後比較交換之前和交換之後的時間開銷。
設當前已經排了d秒，接下來任務是(a1,b1),(a2,b2)
則有d+a1+b1*d+a2+b2*(d+a1+b1*d) <= d+a2+b2*d+a1+b1*(d+a2+b2*d)
消元後，有b2*a1 <= b1*a2
即a1/b1 <= a2/b2
所以將任務按ai/bi從小到大排序即可得到最優解。
 
在標程實現中，用叉積代替了除法防止精度問題。
由於順序可以決定，因此計算過程中直接取mod

[cpp] 
#include <cstdio> 
#include <cstring> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
const int MAXN = 100005; 
const int MOD = 365 * 24 * 60 * 60; 
 
struct Node 
{ 
    int a, b; 
} node[MAXN]; 
 
bool operator < (const Node &a, const Node &b) 
{ 
    return 1LL * a.a * b.b < 1LL * a.b * b.a; 
} 
 
int main() 
{ 
    int n; 
    while(scanf("%d", &n), n) 
    { 
        for(int i=0;i<n;++i) 
        { 
            scanf("%d%d", &node[i].a, &node[i].b); 
        } 
        sort(node, node + n); 
        long long time = 0; 
        long long count = 0; 
        for(int i=0;i<n;++i) 
        { 
            count += node[i].a + time * node[i].b; 
            time += node[i].a + time * node[i].b; 
            count %= MOD; 
            time %= MOD; 
        } 
        cout << count << endl; 
    } 
    return 0; 
}