c318: rilak的期末考前傳

2019-08-23

內容

rilak 正在準備期末考，他只有 T 單位的時間，但卻有 N 個章節要讀，每個章節讀一遍要花 1 單位的時間。

已知 rilak 讀每個章節可以讓他在考試中獲得的分數不同。

另外，同一個章節每多讀一遍，可以獲得的分數都會比上一遍還少。

假設第 i 個章節，rilak 讀第一遍可以獲得 Si 的分數，之後每一遍都會比上一遍少 Di 的分數

舉例來說，Si = 7, Di=3，第一到三遍依序可以獲得 7 分、 4 分、1 分，接下來無論讀幾遍都不會獲得分數(增加 0 分)

rilak 想知道他最多可以獲得多少分？

輸入

第一行有兩個數 N T，N 代表章節數，T 代表有多少單位的時間。

接下來 N 行，每行都有兩個數 Si Di

Si 代表第 i 個章節讀第一遍可以獲得的分數，

Di 代表第 i 個章節多讀一遍比上一遍少得多少分。

對於 100%的測資，保證

1<=N<=1000

1<=T<=1000

1<=Si<=500

1<=Di<=100

2 4
10 5
7 3

輸出

輸出一個整數，表示 rilak 最高可以獲得多少分。

26

解題思路

每次都取最大值，加進總分後將最大值遞減，如此循環直到時間歸 0。

標準的 heap sort 題，不過由於測資薄弱，就算每次都遍歷整個陣列找最大值也能輕鬆過就是了。

完整程式碼

AC (2ms, 108KB)

#include <stdio.h>
#define SWAP(x, y) (x)^=((y)^=((x)^=(y)))

typedef struct Node
{
    int score, dec;
} Node;

Node heap[1010];

int last, now, base, derived;

void swapNode(int lhs, int rhs)
{
    SWAP(heap[lhs].score, heap[rhs].score), SWAP(heap[lhs].dec, heap[rhs].dec);
}

void insNode()
{
    last++;
    scanf(" %d %d", &heap[last].score, &heap[last].dec);
    now = last, base = now >> 1;
    while (base && heap[now].score > heap[base].score)
        swapNode(now, base), now >>= 1, base >>= 1;
}

void heapify()
{
    now = 1, derived = 2;
    while (derived <= last)
    {
        if (heap[derived].score < heap[derived + 1].score && derived < last)
            derived++;
        if (heap[derived].score < heap[now].score)
            break;
        swapNode(now, derived), now = derived, derived <<= 1;
    }
}

int main()
{
    int n, t, ans;
    while (scanf(" %d %d", &n, &t) == 2)
    {
        ans = last = 0;
        while (n--)
            insNode();
        while (t--)
        {
            ans += heap[1].score;
            heap[1].score -= heap[1].dec;
            heapify();
            if (last && heap[last].score <= 0)
                last--;
        }
        printf("%d\n", ans);
    }
    return 0;
}