#36774: 兩種解法


liaoweichen1024@gmail.com (M_SQRT)

學校 : 新北市立新莊高級中學
編號 : 195452
來源 : [210.71.71.103]
最後登入時間 :
2024-05-06 12:16:25
c318. rilak的期末考 前傳 | From: [118.150.177.13] | 發表日期 : 2023-08-08 02:04

本題使用Greedy策略,以下提供兩種撰寫方式

1. PriorityQueue(優先佇列)
每次都取出當前的最大值,PriorityQueue就是用來處理這種情況的,不過PriorityQueue預設的Comparator是'<',我們需要將其改為'>'。

2. 陣列模擬
創建一個陣列,使我們可以查找「多少章的閱讀」能夠獲得此分數。
//這句話這樣講好像會讓人看不太懂,不過我實在沒想到更好的講法,繼續看下去吧,看完就懂了~

題目限制1<=Si<=500,故創建int data[501] = {};
當輸入7 3時,我們可以得知此章能夠讓我們獲得7, 4, 1分,我們在data[7], data[4], data[1]各做+1的動作

處裡完所有輸入後,我們便可得知,針對n分,我們最多可以加data[n]次,此時我們便可以從大到小計算rilak要讀的章節:
for(n=500; n>0; n--)
    if((t-=data[n])<0) {        //已經沒有夠的時間讀data[n]次了
        ans += (data[n]+t)*n;
        break;
    }else ans += data[n]*n;    //讀data[n]次,每次得n分

這個方法寫起來會比PriorityQueue快不少,不過它只適合用在數值不大的情況,PriorityQueue依舊是一個值得認識的工具。


希望這篇解題報告能幫助到你^_^

 
ZeroJudge Forum