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; 
}