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