HDUPhysical Examination（貪心）

HDUPhysical Examination（貪心）

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