HDUPhysical Examination（贪心）

题目大意：给N个队列，每一个队列在0时刻体检的时候完毕时间是ai。假设超过t(s)，那么就是ai + t∗bi.问如何组合才干用最短的时间完毕体检（每一个队列都要去一趟）。

结果要取模一个给定的数。

解题思路：相邻交换法。将这N个队列排下先后体检的顺序。然后在计算要花费的时间就能够了，要用long Long，ai∗bi会int溢出。

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int maxn = 1e5 + 5;const int MOD = 31536000;struct Queue {    ll ai, bi;} q[maxn];bool cmp (const Queue A, const Queue B) {    if (A.ai * B.bi < A.bi * B.ai)        return true;    return false;}int main () {    int n;        while (scanf ("%d", &n) && n) {        for (int i = 0; i < n; i++)            scanf ("%I64d%I64d", &q[i].ai, &q[i].bi);        sort (q, q + n, cmp);        ll ans = q[0].ai, t = q[0].ai;        for (int i = 1; i < n; i++) {            ans = (ans + q[i].ai + (t * q[i].bi) %MOD)%MOD;            t = (t + q[i].ai + (t * q[i].bi) % MOD) % MOD;        }        printf ("%I64d\n", ans);    }    return 0;}